Question

Hay $n$ matemáticos sentados alrededor de una mesa circular con $n$ asientos numerados $1,$ $2,$ $3,$ $\ldots,$ $n$ en sentido horario. Tras un descanso, vuelven a sentarse alrededor de la mesa. Los matemáticos observan que existe un entero positivo $a$ tal que:

primero, para cada $k,$ el matemático que estaba sentado en el asiento $k$ antes del descanso queda sentado en el asiento $ka$ después del descanso (donde el asiento $i + n$ es el asiento $i$ );

segundo, para cada par de matemáticos, el número de matemáticos sentados entre ellos después del descanso, contando tanto en sentido horario como antihorario, es distinto de cualquiera de los números de matemáticos sentados entre ellos antes del descanso.

Halla el número de valores posibles de $n$ con $1 \lt n \lt 1000.$

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

(1) for each $k,$ the mathematician who was seated in seat $k$ before the break is seated in seat $ka$ after the break (where seat $i + n$ is seat $i$ );

(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 $n$ with $1 \lt n \lt 1000.$

Respuesta

Solución:

La condición (1) exige que los asientos $a, 2a, \ldots, na$ sean distintos dos a dos módulo $n,$ lo cual ocurre si y solo si $\gcd(a, n) = 1.$ Para la condición (2), los dos matemáticos de los asientos $i$ y $j$ tienen conteos de separación antes del descanso determinados por $\pm(i - j) \bmod n$ y después del descanso por $\pm a(i - j) \bmod n,$ así que el requisito es $a(i - j) \not\equiv \pm(i - j) \pmod{n}$ para todo $i \ne j.$ De forma equivalente, $(a - 1)(i - j) \not\equiv 0$ y $(a + 1)(i - j) \not\equiv 0 \pmod{n}$ para todo residuo no nulo $i - j,$ lo cual se cumple exactamente cuando $a - 1$ y $a + 1$ también son coprimos con $n.$

Así, $n$ es posible si y solo si algún $a$ satisface $\gcd\big((a - 1)\,a\,(a + 1),\, n\big) = 1.$ Tres enteros consecutivos cualesquiera incluyen un múltiplo de $2$ y un múltiplo de $3,$ así que ningún $a$ funciona cuando $\gcd(n, 6) \gt 1.$ Recíprocamente, si $\gcd(n, 6) = 1,$ entonces $a = 3$ funciona, ya que $2 \cdot 3 \cdot 4 = 24$ solo tiene los factores primos $2$ y $3.$

Los $n$ válidos con $1 \lt n \lt 1000$ son los congruentes con $\pm 1 \pmod 6,$ es decir, $6k \pm 1$ para $1 \le k \le 166,$ y hay $2 \cdot 166 = 332$ de ellos.

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

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

The valid $n$ with $1 \lt n \lt 1000$ are those congruent to $\pm 1 \pmod 6,$ namely $6k \pm 1$ for $1 \le k \le 166,$ and there are $2 \cdot 166 = 332$ of them.

2012 AIME I Problema 15

Solución:

El Problema 15 en otros años