2012 AIME I Problem 15

Below is the professionally curated solution for Problem 15 of the 2012 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2012 AIME I solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticgreatest common divisor

Difficulty rating: 3370

15.

There are nn mathematicians seated around a circular table with nn seats numbered 1,1, 2,2, 3,3, ,\ldots, nn in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer aa such that

(1) for each k,k, the mathematician who was seated in seat kk before the break is seated in seat kaka after the break (where seat i+ni + n is seat ii);

(2) for every pair of mathematicians, the number of mathematicians sitting between them after the break, counting in both the clockwise and the counterclockwise directions, is different from either of the number of mathematicians sitting between them before the break.

Find the number of possible values of nn with 1<n<1000.1 \lt n \lt 1000.

Solution:

Condition (1) requires the seats a,2a,,naa, 2a, \ldots, na to be pairwise distinct modulo n,n, which happens if and only if gcd(a,n)=1.\gcd(a, n) = 1. For condition (2), the two mathematicians from seats ii and jj have gap counts before the break determined by ±(ij)modn\pm(i - j) \bmod n and after the break by ±a(ij)modn,\pm a(i - j) \bmod n, so the requirement is a(ij)≢±(ij)(modn)a(i - j) \not\equiv \pm(i - j) \pmod{n} for all ij.i \ne j. Equivalently, (a1)(ij)≢0(a - 1)(i - j) \not\equiv 0 and (a+1)(ij)≢0(modn)(a + 1)(i - j) \not\equiv 0 \pmod{n} for every nonzero residue ij,i - j, which holds exactly when a1a - 1 and a+1a + 1 are also relatively prime to n.n.

So nn is possible if and only if some aa satisfies gcd((a1)a(a+1),n)=1.\gcd\big((a - 1)\,a\,(a + 1),\, n\big) = 1. Any three consecutive integers include a multiple of 22 and a multiple of 3,3, so no aa works when gcd(n,6)>1.\gcd(n, 6) \gt 1. Conversely, if gcd(n,6)=1,\gcd(n, 6) = 1, then a=3a = 3 works, since 234=242 \cdot 3 \cdot 4 = 24 has only the prime factors 22 and 3.3.

The valid nn with 1<n<10001 \lt n \lt 1000 are those congruent to ±1(mod6),\pm 1 \pmod 6, namely 6k±16k \pm 1 for 1k166,1 \le k \le 166, and there are 2166=3322 \cdot 166 = 332 of them.

← Problem 14Full Exam

Problem 15 in Other Years