Chicos, no esperen ninguna belleza matemática sobresaliente o algoritmos útiles en la vida. Le escribo por puro interés deportivo. Me interesó el problema aquí publicado , con el que los presos estadounidenses se divierten sus enormes condenas. A juzgar por los comentarios al artículo, ya ha despertado cierto interés en la comunidad. Entiendo que no lo estoy haciendo muy bien, debería haberle dado a la gente tiempo para pensar por sí mismos. Sin embargo, me arrepiento, soy un pecador, no puedo resistir. Y publico mi decisión aquí. A quién le importa, bienvenido a cat. Si quieres pensar un poco más por tu cuenta, no lo leas todavía.
Entonces, la tarea en sí. Lo formularé con un poco más de claridad que en el artículo mismo (por desgracia, la traducción es un poco torcida).
El dial (como en la Figura 1) puede apuntar a cualquier número entero de 1 an cuando se gira en sentido antihorario. La cuenta regresiva comienza desde 1, luego la flecha gira secuencialmente (siempre en sentido antihorario) una posición, luego dos, luego tres, y así sucesivamente, hasta el último giro en la posición n-1. Recopilamos la secuencia de todos los números señalados por la flecha.
Por ejemplo, si n = 12, obtienes la secuencia 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Se puede ver que hay números repetidos en ella.
Y para n = 8, la secuencia será 1, 2, 4, 7, 3, 8, 6, 5. Y no hay números repetidos en ella.
La pregunta es, ¿para qué valores de n no se repiten los números de la secuencia?
Presentado por Gary Gordon y Denise Ozbay, noviembre de 2020, Mathematical Horizons.
Llamemos a la secuencia, que se construye en el problema, la secuencia del n-dial . Y los números, n para los cuales esta secuencia no contiene números repetidos, son adecuados .
Comencemos por recibir un consejo muy serio. Respuesta preparada casi de inmediato. No fui a las cárceles estadounidenses y no sé si los reclusos tienen computadoras disponibles. ¡Pero tengo mi caballo de guerra en mi mesa! Entonces es un pecado no usarlo. Lanzamos nuestro cuaderno jupyter favorito y entramos en un pequeño programa:
def getSeq(n): # n-
lst=[]
s=1 #
d=1 #
for i in range(0, n):
lst.append(s)
s=(s+d) % n
if s==0:
s=n
d=d+1 # 1
return lst
def testSeq(lst): #
if len(set(lst)) == len(lst):
return True
return False
def getList(n): # , 2 n
lst=[]
for i in range(2, n):
if testSeq(getSeq(i)):
lst.append(i)
return lst
Al ejecutar getList (12345) se obtiene una lista de 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Por lo tanto, parece muy probable que solo las potencias de dos sean números válidos, y nada más. Solo queda probarlo. Más precisamente, deberán probarse dos afirmaciones:
1) Cualquier potencia de dos es un número adecuado.
2) Cualquier número que no sea una potencia de dos no es adecuado.
Primero, veamos de dónde provienen los números repetidos en la secuencia de n-dial.
La secuencia comienza desde 1. Su incremento en el primer paso también es igual a 1, y luego con cada paso aumenta en 1. El resto de la división por n se toma como resultado. Además, si el resto es cero, se supone que el resultado es igual an. Intentemos construir tal secuencia para un número n no muy grande. Por ejemplo, n = 6:
s (1) = 1 (mod 6) = 1
s (2) = 1 + 1 (mod 6) = 2
s (3) = 2 + 2 (mod 6) = 4
s (4) = 4 + 3 (modo 6) = 7 (modo 6) = 1
s (5) = 7 + 4 (modo 6) = 11 (modo 6) = 1 + 4 (modo 6) = 5
s (6) = 11 + 5 (módulo 6) = 16 (módulo 6) = 5 + 5 (módulo 6) = 4
Vemos que coincidieron dos pares: s (1) y s (4), y s (3) y s (6). Además, si tomamos los valores no módulo, la diferencia entre los elementos mayor y menor de ambos pares es un múltiplo de 6. Eso, en general, es bastante comprensible. El valor final se toma módulo n. Y si, antes de tomar el módulo, los números difieren en n (o un múltiplo de n), entonces los valores finales coincidirán.
Por otro lado, dado que el incremento que tenemos en cada paso aumenta en 1. Y es claro que las diferencias anteriores son iguales a las sumas de algunos números consecutivos. Por ejemplo, para el par s (1), s (4):
7 = 1 + (1 + 2 + 3)
Y para el par s (3), s (6):
16 = 4 + (3 + 4 + 5)
Para el primero, la diferencia es 6 para el par y 12 para el segundo
, por lo que llegamos a una importante conclusión:
Si aparecen números coincidentes en la secuencia del dial n, entonces no su múltiplo se puede representar como una suma de algunos números consecutivos, el mayor de los cuales no excede el número n-1.
Primero, probamos un enunciado auxiliar:
cualquier número que no sea una potencia de dos puede representarse como una suma de números consecutivos. Ninguna potencia de dos puede representarse mediante la suma de números consecutivos.
Pensemos en cómo representar generalmente un número como una suma de números consecutivos. Para los extraños, esto es bastante simple. Si A es impar, entonces se puede representar con un par:
A = [A / 2] + ([A / 2] + 1), donde [] significa la parte entera del número.
Por ejemplo, 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
Es solo eso para múltiplos de 3. Si A es un múltiplo de 3, entonces:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
De manera similar, si A es un múltiplo de 5:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
Y, en general, si el número A tiene un divisor impar B, se puede representar como una suma de B números consecutivos y el número A / B está exactamente en el medio.
Ejemplos:
27 = 3 * 9. Por tanto, 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10,50
= 5 * 10. Por tanto, 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
Lo contrario también es obvio. Si un número se puede representar como la suma de un número impar de números consecutivos, entonces tiene un divisor impar y la representación en sí tiene la forma descrita anteriormente. Por tanto, la potencia de dos no puede ser la suma de un número impar de números consecutivos , porque no tiene divisores impares.
Pero, ¿qué pasa con la suma de un número par de números consecutivos? La suma de dos números consecutivos siempre es impar. Es de esperar que esto sea obvio. La suma de cuatro se puede considerar como la suma de dos pares, cada uno de los cuales es impar. Entonces la suma de cuatro es par. La suma de seis es nuevamente impar, la suma de ocho es par, y así sucesivamente. Aquellos. la suma de un número par de números consecutivos es par si su número es un múltiplo de 4 e impar si es un múltiplo de solo 2.
Sea un número par A la suma de 4 * k números consecutivos. Para simplificar, sea k = 1, para k grande el razonamiento es completamente análogo:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Divida esta igualdad por 2 :
A / 2 = (4 * a + 6) / 2 = 2 * a + 3 = (a + 1) + (a + 2).
Aquellos. de nuevo obtenemos la suma de números consecutivos.
Por lo tanto, si para un número par A hay una representación en forma de suma de un número par de números consecutivos, entonces existe alguna representación en forma de suma de números consecutivos para A / 2 .
Por ejemplo:
26 = 5 + 6 + 7 + 8. Por tanto, 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Suponga que para la N-ésima potencia de dos hay una representación en forma de suma de un número par de números consecutivos (no hay representación en forma de número impar como se muestra arriba). Luego hay una representación en forma de suma de números consecutivos para el grado N-1. Y el número de términos en él también es par. Por inducción, se puede decir lo mismo del grado N-2 y del grado N-3 y, en general, de cualquier grado menor que N. Pero no hay representación en forma de suma de números consecutivos para el número 4, que es fácil de ver. Por lo tanto, ninguna potencia de dos puede representarse como una suma de números consecutivos .
Por otro lado, cualquier número que no sea una potencia de dos se puede representar como una suma de números consecutivos. Si este número es impar, se puede representar como un par. Si es par y no una potencia de dos, entonces tiene al menos un divisor impar. Y representable a través de él.
Se prueba el enunciado auxiliar.
Considere la secuencia completa de n-dial.
s (1) = 1 (modelo n)
s (2) = 1 + 1 (modelo n)
s (3) = 2 + 2 (modelo n)
s (4) = 4 + 3 (modelo n)
…
s (n ) = s (n-1) + n-1 (mod n)
Sea n una potencia de dos. Entonces 2 * n, 4 * n, 8 * n, etc., también son potencias de dos. Y como suma de números consecutivos, no son representables. Representables son 3 * n, 5 * n, 6 * n, 7 * n, 9 * n, etc. Aquellos. el número m * n debe tener al menos un divisor impar. Sin embargo, incluso el más pequeño de estos múltiplos, 3 * n, debe representarse como
(n - 1) + n + (n + 1).
No hay otras representaciones del número 3 * n. Porque n como una potencia de dos no tiene representaciones en absoluto (vea la declaración auxiliar). Pero los términos en esta suma no deben exceder el número n - 1. Por lo tanto, 3 * n como diferencia nunca aparecerá. Para otros múltiplos, el razonamiento es exactamente el mismo. Por supuesto, ni n ni 2 * n aparecerán tampoco como diferencias, como potencias de dos. Entonces, cualquier potencia de dos es un número adecuado.
Se prueba el enunciado (1).
Ahora, no sea una potencia de dos. Aquellos. representable como una suma de números consecutivos. La diferencia entre el primero y el último miembro de la secuencia (antes de tomar el módulo por n) será:
d = 1 + 2 + 3 +… + (n-1).
Y las diferencias entre los miembros de la secuencia n-dial (antes de tomar el módulo) serán las sumas parciales de esta serie. Si n se puede representar como una suma de números consecutivos, entonces los números más grandes posibles que componen dicha suma son
[n / 2] y [n / 2] + 1. ([] es la parte entera de un número)
Todos los demás variantes de tal suma se componen de números aún más pequeños ... Esto significa que los miembros de la secuencia del n-dial, con una diferencia antes de tomar el módulo igual an, ciertamente se encontrarán. Y después de tomar el módulo, darán los números correspondientes. Aquellos. cualquier n que no sea una potencia de dos, y por lo tanto representable como una suma de números consecutivos, no es un número adecuado.
Se prueba el enunciado (2).
En total, la tarea está completamente resuelta. Los números adecuados son potencias de dos y no otras. ¡¡¡A la libertad con la conciencia tranquila !!!
La moraleja de esta fábula es quizás solo una. Chicos, incluso si hacen matemáticas puras, no descuiden los experimentos computacionales. Sí, tales experimentos no prueban nada. Sin embargo, pueden dar una conjetura bien fundada. Aunque puede que no sea tan simple como aquí. Y probar suele ser mucho más fácil que adivinar. Me alegraría que alguien encontrara esta presentación útil e interesante.