Tablero: 1, 2, 3, 4, 5, 6, 7 …
Borrar: 1, 3, 5, 7, 9 …
Regla: borra todos los 2n-1 donde n = 1, 2, 3, 4 …
—-
- ¿Qué es más eficiente para encontrar una solución para el problema del vendedor ambulante, una búsqueda puramente aleatoria o un algoritmo genético? ¿Hay un papel?
- Cómo asignar el antiguo objeto vectorial al objeto vectorial en C ++
- ¿Cómo particionar un conjunto múltiple de enteros positivos en tres subconjuntos de modo que se minimice la diferencia entre las sumas de subconjuntos máximas y mínimas?
- ¿Cuáles son algunas aplicaciones del algoritmo Aho Corsaik en la programación competitiva?
- Cómo resolver [matemáticas] x + y + z = a, x ^ 2 + y ^ 2 + z ^ 2 = b, x ^ 3 + y ^ 3 + z ^ 3 = c [/ matemáticas] para [matemáticas] x , y, z [/ matemáticas]
Tablero: 2, 4, 6, 8, 10, 12 …
Borrar: 2, 6, 10, 14 …
Regla: borra todos los 4n-2 donde n = 1, 2, 3, 4 …
—-
Tablero: 4, 8, 12, 16, 20 …
Borrar: 4, 12, 20, 28 …
Regla: borra todos los 8n-4 donde n = 1, 2, 3, 4 …
—-
Tablero: 8, 16, 24, 32, 40 …
Borrar: 8, 24, 40, 56 …
Regla: Borrar todos los 16n-8 donde n = 1, 2, 3, 4 …
—-
Como puede ver, está surgiendo un patrón.
La regla para la ronda 1 es borrar cualquier número que sea 2n-1.
La regla para la ronda 2 es borrar cualquier número que sea 4n-2 o 2 (2n-1).
La regla para la ronda 3 es borrar cualquier número que sea 8n-4 o 4 (2n-1).
La regla para la ronda 4 es borrar cualquier número que sea 16n-4 u 8 (2n-1).
En general, durante la ronda R, borre cualquier número que sea 2 ^ (R-1) * (2n-1)
—-
¿Cuándo se borra 1728?
2 ^ (R-1) * (2n-1) = 1728
Como n puede ser cualquier número entero,
por lo tanto 2n es un número par
por lo tanto (2n-1) es un número impar
La factorización prima de 1728 es 2 ^ 6 * 3 ^ 3
2 ^ 6 = 2 ^ (R-1) y 3 ^ 3 = (2n-1)
Sé esto porque (2n-1) debe ser impar, por lo que no puede tener ningún 2 en sus factores, y 2 ^ (R-1) debe contener solo 2. Como (2n-1) no puede contener ningún 2, entonces 2 ^ (R-1) debe contener todos los 2.
2 ^ 6 = 2 ^ (R-1) es la parte que queremos resolver porque contiene R.
R = 7
1728 se borra en la ronda 7.
—-
¿Qué número se borró al final?
Esto tomó un poco de pensamiento. El último número borrado es cuando la fórmula:
2 ^ (R-1) * (2n-1)
solo puede borrar un número.
Eso significa que cuando establece n = 1, ese número es el último en borrarse.
También significa que cuando establece n = 2, ese número es mayor que 2009.
En caso de que esto no tenga sentido, lo que quiero decir es que la fórmula puede borrar infinitos números, la única restricción es que no puede borrar números mayores que 2009 porque no están en el tablero. Entonces, en cierta ronda R, la fórmula solo produce un número dentro de 1–2009 si n = 1. En n = 2, la fórmula produce un número mayor que 2009, lo cual ignoramos.
2 ^ (R-1) * (2 (2) -1)> 2009
2 ^ (R-1)> 669,67
Desde aquí podemos usar log, o algo aún más simple:
2 ^ (R-1)> 1024
Eso solo es cierto porque R es un número entero, y la potencia más pequeña de 2 mayor que 669.67 es 1024.
2 ^ (R-1)> 2 ^ 10
R = 11
Por lo tanto 2 ^ (R-1) * (2 (1) -1) = 1024
En la ronda 11, 1024 es el último número que se borrará.