USAMTS $4/2/17$ Pato ganso ganso problema

Question

Este es el problema de USAMTS:

Un profesor juega el juego de "Pato-Ganso-de Ganso" con los de su clase. El juego se juega como de la siguiente manera: Todos los estudiantes de pie en un círculo y el maestro camina alrededor del círculo. Como él pasa cada estudiante, se aprovecha del estudiante en la cabeza y declara su 'pato' o un 'ganso'. Cualquier estudiante que se denomina un 'ganso' deja el círculo de inmediato. Comenzando con el primer estudiante, el maestro de las etiquetas de los estudiantes en el patrón de pato, de ganso, ganso, pato, ganso, ganso, etc., y continúa alrededor del círculo (re-etiquetado de algunos ex patos como los gansos) hasta que sólo uno de los estudiantes sigue siendo. Este resto de los estudiantes es el ganador. Por ejemplo, si hay $8$ estudiantes, el juego se desarrolla de la siguiente manera: el estudiante $1$ (pato), estudiante de $2$ (oca), estudiante de $3$ (oca), estudiante de $4$ (pato), estudiante de $5$ (oca), estudiante de $6$ (oca), estudiante de $7$ (pato), estudiante de $8$ (oca), estudiante de $1$ (oca), estudiante de $4$ (pato), estudiante de $7$ (oca) y el estudiante de $4$ es el ganador. Encontrar, con la prueba, todos los valores de $n$ $n > 2$ de manera tal que si el el círculo comienza con $n$ de los estudiantes, entonces el $n$ th estudiante es el ganador.

He visto el caso de $n=2$ en un Numberphile video que si se expresa en base a $2,$ acaba de tomar el primer dígito y lo puso en la parte inferior, también llamado el problema de Josefo.

¿Cómo se puede aplicar la misma lógica aquí?

En la actualidad, me di cuenta de que $3^n$ posición $1$ ganar cada vez, así que sospecho que el patrón aún se mantiene, pero no puedo demostrarlo.

Answer 1

En el primer paso de todo el círculo, estudiante $i$ $(i$ que van desde la $1$$n)$, quedará excluida si y sólo si $i \equiv 0$ o $i\equiv 2\pmod 3$. En otras palabras, para el $n$-th estudiante para evitar la exclusión, debemos tener $n\equiv 1 \pmod 3$.

Supongamos que, por ende,$n = 3k+1$. Después de la marcación de cada estudiante exactamente una vez, estamos en un círculo con $k+1$ a los estudiantes, por lo que si $k=0$, el juego termina inmediatamente después de este primer paso.

---

Supongamos que, por ende,$k>0$, por lo que el juego continuará. En este caso, el $n$-ésimo alumno es ahora el $(k+1)$-th.

Ahora, el maestro del patrón comienza con Ganso Ganso Pato. Esto significa que si $k+1\leqslant 3$, $n$- ésimo alumno va a sobrevivir como resultado de todos los demás en el etiquetado de Ganso delante de él.

---

Si $k+1>3$, luego vamos a hacer un recorrido completo alrededor del círculo. De ello se sigue que el estudiante $i$ $(i$ que van desde la $1$ $k+1)$va a ser excluido si y sólo si $i \equiv 1$ o $i\equiv 2\pmod 3$. Por lo tanto, para el $(k+1)$-th estudiante para evitar la exclusión, debemos tener $k+1 \equiv 0 \iff$ $k \equiv2 \pmod 3$.

Supongamos que, por ende,$k = 3j+2$, por lo que tuvimos $3j+3$ de los estudiantes. Recuerde que para llegar a este punto, hemos tenido que asumir $k+1>3$, por lo que, necesariamente,$j>0$.

---

Estamos ahora reducido a $j+1$ estudiantes y el $n$-ésimo alumno es ahora el $(j+1)$-th.
El patrón una vez más seres con Ganso Ganso Pato, así que esto va exactamente igual que antes: cualquiera de las $j+1\leqslant 3$ e las $n$-th estudiantes sobrevive de otros comienzan etiquetado de Ganso delante de él; o bien debemos tener $j\equiv 2 \pmod 3$ a fin de $n$ para evitar la exclusión.

Por supuesto, este patrón se repita.

---

Nuestra posible $n$ por lo tanto se

• $1$ $k=0$
• $4,7$ $k=1,2$ $k+1\leqslant 3$
• $16, 25$ $j=1,2$ $j+1 \leqslant 3$

y si seguimos en esta moda de ahora vamos a tener que agregar $27=3^3$ $25$obtener $n=52$, y, a continuación,$52+27 = 79$. Procedimiento tendremos $79 + 3^4 = 160$ y, a continuación,$160 + 81 = 241$, y así sucesivamente y así sucesivamente.

---

Una forma compacta de considerar los posibles valores de $n$ es, por tanto, considerar la infinita suma

\begin{align} \begin{array}{}&1&+&3&+&3&+&9&+&9&+&27&+&27&+&81&+&81&+&\dots\\ =&3^0&+&3^1&+&3^1&+&3^2&+&3^2&+&3^3&+&3^3&+&3^4&+&3^4&+&\dots\end{array} \end{align}

Cualquier $n$ pueden ser obtenidos de esta infinita suma por truncar. Esto sugiere, tal vez más que la representación formal en los términos del ternario de la base de la representación:

$$n = \sum_{i=0}^k\,a_i\,3^i,$$

donde $k\geqslant 0$ y $a_0 = 1$, $a_j = 2$ para todos los $0<j<k$$a_k \in \{1,2\}$.

Answer 2

Escribimos los números de $0$ $N:=n-1$en la base de los tres. El primer numero es 00...000.

Deje $k$ el número de dígitos de $n-1$.

Deje que D estancia para "pato" y " G " para "ir". La última, $n$.th estudiante gana, a continuación, con uno de los siguientes las últimas palabras del maestro:

D = GGD = DGGD, o DG = DGGDG .

Luego de un fijo $k$ sólo hay un correspondiente ganadora $N$ que gana como D, respectivamente DG a saber

22...220 respectively
12...220

(con $k$ dígitos).

Prueba. Llamamos a un paso, una ronda el procedimiento de eliminación para cada grupo de estudiantes, se mantuvo entre ellos, con la etiqueta de un a $n$, y pasamos a la nueva etapa, cuando la etiqueta gotas.

Asumimos que el estudiante $n$ gana, consiguiendo una condición necesaria para ser verificada.

Después de la primera vuelta en el círculo de sobrevivir el primer estudiante, con la etiqueta 00...000, y a todos aquellos de la forma *0, por lo que el $n$.th estudiante es en esta forma. Ahora no son sólo los estudiantes *0 en la lista como el maestro pronuncia el "pato" en el último estudiante en la "primera ronda", ahora el "resto" de dos, pronuncia ganso ganso, el primer estudiante se mantuvo en la segunda ronda es 00...020, y por lo tanto sólo el *20 estudiantes de sobrevivir. Por lo que el $n$.th estudiante es un estudiante, se convierte en D, de modo que el primer D en la siguiente ronda es 00...0220, por lo que no sobrevivirá a todos los *220 estudiantes. Esto va en la, ronda por ronda, quedan en el concurso solo

*0      after 1.st round
*20     after 2.nd round
*220    after 3.rd round
*2220   after 4.th round
*22220  after 5.th round

y así sucesivamente, por supuesto cada vez que si había tantas rondas. Ahora queda por analizar lo que sucede cuando el primer dígito en base de tres se convierte en relevante. Así que sabemos que $N$ es de la forma

122...220 or
222...220

y ver que en ambos casos son ganancia para la $n$.th estudiante. (Como DG, respectivamente DGGD = D = DGG.) Esta comprobación también se borra el conversar implicación. (Estábamos asumiendo todo el tiempo que $n$ wins).

La adición de $3=$10${}_3$ a los números anteriores obtenemos 200...000 y 1000...000. Nos encontramos, pues, $N=2\cdot 3^{k-1}-3$ o $N=3\cdot 3^{k-1}-3$. La adición de uno, tenemos $n=2\cdot 3^{k-1}-2$ o $n=3^k-2$.

---

Equipo de verificación, aquí sabio, lento código:

def winner(n):
    L = [1..n]
    while len(L) > 3:
       L = L[3:] + [L[0]]
    return L[0]

for n in [2..3^7]:
    if n == winner(n):
       print "Solution n = %4s with digits %s" % (n, n.digits(base=3))

Resultados (con los dígitos que viene en orden inverso):

Solution n =    4 with digits [1, 1]
Solution n =    7 with digits [1, 2]
Solution n =   16 with digits [1, 2, 1]
Solution n =   25 with digits [1, 2, 2]
Solution n =   52 with digits [1, 2, 2, 1]
Solution n =   79 with digits [1, 2, 2, 2]
Solution n =  160 with digits [1, 2, 2, 2, 1]
Solution n =  241 with digits [1, 2, 2, 2, 2]
Solution n =  484 with digits [1, 2, 2, 2, 2, 1]
Solution n =  727 with digits [1, 2, 2, 2, 2, 2]
Solution n = 1456 with digits [1, 2, 2, 2, 2, 2, 1]
Solution n = 2185 with digits [1, 2, 2, 2, 2, 2, 2]