1993 AIME Problema 9

Question

Hay dos mil puntos sobre un círculo. Marca uno de ellos con

1.

Desde ese punto, cuenta

2

puntos en sentido horario y marca el punto alcanzado con

2.

Desde el punto marcado con

2,

cuenta

3

puntos en sentido horario y marca el punto alcanzado con

3.

(Véase la figura). Continúa este proceso hasta usar todas las marcas

1,

2,

3,

\ldots,

1993.

Algunos puntos del círculo tendrán más de una marca y otros no tendrán ninguna. ¿Cuál es el menor entero que marca el mismo punto que

1993

?

Two thousand points are given on a circle. Label one of the points

1.

From this point, count

2

points in the clockwise direction and label this point

2.

From the point labeled

2,

count

3

points in the clockwise direction and label this point

3.

(See figure.) Continue this process until the labels

1,

2,

3,

\ldots,

1993

are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as

1993?

Respuesta

Respuesta: 118

Conceptos:Teorema chino del resto aritmética modular residuo cuadrático

Nivel de dificultad: 2550

Pista pequeña:

Mide el desplazamiento horario de cada marca desde el punto marcado con

1

Measure every label’s clockwise displacement from the point labeled

1

Pista grande:

Reduce la congruencia cuadrática resultante por separado módulo

32

y módulo

125

Reduce the resulting quadratic congruence separately modulo

32

and modulo

125

Solución:

La marca

j

está desplazada

2+3+\cdots+j=\frac{j(j+1)}2-1

puntos en sentido horario desde la marca

1.

Por lo tanto, comparte el punto de la marca

1993

exactamente cuando

j(j+1)\equiv1993\cdot1994

módulo

4000,

o, de manera equivalente, cuando

j(j+1)\equiv2042\pmod {4000}.

Módulo

125,

las soluciones son

j\equiv6

y

j\equiv118,

y módulo

32,

son

j\equiv9

y

j\equiv22.

Al combinarlas mediante el teorema chino del resto se obtiene

\begin{aligned}j\equiv{}&118,1993,\\&2006,3881\pmod {4000}.\end{aligned}

La menor posibilidad positiva es

118.

Label

j

is displaced

2+3+\cdots+j=\frac{j(j+1)}2-1

points clockwise from label

1.

Thus it shares the point of label

1993

exactly when

j(j+1)\equiv1993\cdot1994

modulo

4000,

or equivalently when

j(j+1)\equiv2042\pmod {4000}.

Modulo

125,

the solutions are

j\equiv6

and

j\equiv118,

and modulo

32,

they are

j\equiv9

and

j\equiv22.

Combining these by the Chinese Remainder Theorem gives

\begin{aligned}j\equiv{}&118,1993,\\&2006,3881\pmod {4000}.\end{aligned}

The smallest positive possibility is

118.