Les gars, ne vous attendez pas à des beautés mathématiques exceptionnelles ou à des algorithmes utiles dans la vie. J'écris par pur intérêt sportif. Je m'intéressais au problème publié ici , avec lequel les prisonniers américains s'éloignaient de leurs énormes peines. À en juger par les commentaires de l'article, il a déjà suscité un certain intérêt dans la communauté. Je comprends que je ne vais pas très bien, j'aurais dû laisser aux gens le temps de penser par eux-mêmes. Cependant, je me repens, je suis un pécheur, je ne peux pas résister. Et je poste ma décision ici. Peu importe, bienvenue au chat. Si vous voulez réfléchir davantage par vous-même, ne le lisez pas encore.
Donc, la tâche elle-même. Je vais le formuler un peu plus clairement que dans l'article lui-même (hélas, la traduction y est un peu tordue).
Le cadran (comme dans la figure 1) peut pointer vers n'importe quel entier de 1 à n lorsqu'il est tourné dans le sens antihoraire. Le compte à rebours commence à 1, puis la flèche tourne séquentiellement (toujours dans le sens antihoraire) d'une position, puis deux, puis trois, et ainsi de suite, jusqu'au dernier tour de position n-1. Nous collectons la séquence de tous les nombres pointés par la flèche.
Par exemple, si n = 12, vous obtenez la séquence 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. On peut voir qu'il contient des nombres répétés.
Et pour n = 8, la séquence sera 1, 2, 4, 7, 3, 8, 6, 5. Et il n'y a pas de nombres répétitifs dedans.
La question est, pour quelles valeurs de n les nombres de la séquence ne sont-ils pas répétés?
Présenté par Gary Gordon et Denise Ozbay, novembre 2020, Mathematical Horizons.
Appelons la séquence, qui est construite dans le problème, la séquence du n-dial . Et les nombres, n pour lesquels cette séquence ne contient pas de nombres répétitifs, conviennent .
Commençons par obtenir une astuce très sérieuse. Réponse presque immédiatement prête à l'emploi. Je ne suis pas allé dans les prisons américaines et je ne sais pas si des ordinateurs sont à la disposition des détenus là-bas. Mais j'ai mon cheval de guerre sur ma table! C'est donc un péché de ne pas l'utiliser. Nous lançons notre notebook jupyter préféré et entrons dans un petit programme:
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
L'exécution de getList (12345) donne une liste de 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Il semble donc très probable que seules les puissances de deux soient des nombres valides, et rien d'autre. Il ne reste plus qu'à le prouver. Plus précisément, deux affirmations devront être prouvées:
1) Toute puissance de deux est un nombre convenable.
2) Tout nombre qui n'est pas une puissance de deux ne convient pas.
Tout d'abord, voyons d'où viennent les nombres répétés dans la séquence n-dial.
La séquence commence à 1. Son incrément au premier pas est également égal à 1, puis à chaque pas il augmente de 1. Le reste de la division par n est pris comme résultat. De plus, si le reste est nul, alors le résultat est supposé égal à n. Essayons de construire une telle séquence pour un nombre n pas très grand. Par exemple 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 (mod 6) = 7 (mod 6) = 1
s (5) = 7 + 4 (mod 6) = 11 (mod 6) = 1 + 4 (mod 6) = 5
s (6) = 11 + 5 (mod 6) = 16 (mod 6) = 5 + 5 (mod 6) = 4
On voit que deux paires coïncident: s (1) et s (4), et s (3) et s (6). De plus, si nous prenons les valeurs non modulo, la différence entre les éléments plus grands et plus petits des deux paires est un multiple de 6. Cela, en général, est tout à fait compréhensible. La valeur finale est prise modulo n. Et si, avant de prendre le module, les nombres diffèrent de n (ou d'un multiple de n), alors les valeurs finales coïncideront.
Par contre, puisque l'incrément que nous avons à chaque pas augmente de 1. Et il est clair que les différences ci-dessus sont égales aux sommes de certains nombres consécutifs. Par exemple, pour le couple s (1), s (4):
7 = 1 + (1 + 2 + 3)
Et pour le couple s (3), s (6):
16 = 4 + (3 + 4 + 5)
Pour le premier, la différence est de 6 pour la paire et de 12 pour le second.
Ainsi, nous arrivons à une conclusion importante:
Si des nombres coïncidents apparaissent dans la séquence du cadran n, alors n ou son multiple peut être représenté comme une somme de quelques nombres consécutifs, dont le plus grand ne dépasse pas le nombre n-1.
Tout d'abord, nous prouvons une instruction auxiliaire:
tout nombre qui n'est pas une puissance de deux peut être représenté comme une somme de nombres consécutifs. Aucune puissance de deux ne peut être représentée par la somme de nombres consécutifs.
Réfléchissons à la façon de représenter généralement un certain nombre comme une somme de nombres consécutifs. Pour les étranges, c'est assez simple. Si A est impair, alors il peut être représenté par une paire:
A = [A / 2] + ([A / 2] + 1), où [] signifie la partie entière du nombre.
Par exemple 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
C'est juste que pour les multiples de 3. Si A est un multiple de 3, alors:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
De même, si A est un multiple de 5:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
Et en général, si le nombre A a un diviseur impair B, il peut être représenté comme une somme de B nombres consécutifs, et le nombre A / B est exactement au milieu.
Exemples:
27 = 3 * 9. D'où 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10,50
= 5 * 10. D'où 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
Le contraire est également évident. Si un nombre est représentable comme la somme d'un nombre impair de nombres consécutifs, alors il a un diviseur impair et la représentation elle-même a la forme décrite ci-dessus. Par conséquent, la puissance de deux ne peut pas être la somme d'un nombre impair de nombres consécutifs , car elle n'a pas de diviseurs impairs.
Mais qu'en est-il de la somme d'un nombre pair de nombres consécutifs? La somme de deux nombres consécutifs est toujours impaire. Ceci est, espérons-le, évident. La somme de quatre peut être considérée comme la somme de deux paires, chacune étant impaire. La somme de quatre est donc égale. La somme de six est encore une fois impaire, la somme de huit est paire, et ainsi de suite. Celles. la somme d'un nombre pair de nombres consécutifs est paire si leur nombre est un multiple de 4, et impaire s'il s'agit d'un multiple de seulement 2.
Soit un nombre pair A la somme de 4 * k nombres consécutifs. Pour simplifier, soit k = 1, pour k grand, le raisonnement est tout à fait analogue:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Diviser cette égalité par 2 :
A / 2 = (4 * a + 6) / 2 = 2 * a + 3 = (a + 1) + (a + 2).
Celles. encore une fois, nous obtenons la somme des nombres consécutifs.
Par conséquent, si pour un nombre pair A il y a une représentation sous la forme de la somme d'un nombre pair de nombres consécutifs, alors une représentation sous la forme d'une somme de nombres consécutifs existe pour A / 2 .
Par exemple:
26 = 5 + 6 + 7 + 8. Donc 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Supposons que pour la Nième puissance de deux, il y ait une représentation sous la forme d'une somme d'un nombre pair de nombres consécutifs (il n'y a pas de représentation sous la forme d'un nombre impair pour elle comme indiqué ci-dessus). Ensuite, il y a une représentation sous la forme d'une somme de nombres consécutifs pour le degré N-1. Et le nombre de termes qu'il contient est également pair. Par récurrence, on peut en dire autant du degré N-2 et du degré N-3 et, en général, de tout degré inférieur à N. Mais il n'y a pas de représentation sous la forme d'une somme de nombres consécutifs pour le nombre 4, ce qui est facile à voir. Par conséquent, aucune puissance de deux ne peut être représentée comme une somme de nombres consécutifs .
D'un autre côté, tout nombre qui n'est pas une puissance de deux peut être représenté comme une somme de nombres consécutifs. Si ce nombre est impair, il peut être représenté par une paire. S'il est pair et non une puissance de deux, alors il a au moins un diviseur impair. Et représentable à travers elle.
La déclaration auxiliaire est prouvée.
Considérez toute la séquence n-dial.
s (1) = 1 (mod n)
s (2) = 1 + 1 (mod n)
s (3) = 2 + 2 (mod n)
s (4) = 4 + 3 (mod n)
…
s (n ) = s (n-1) + n-1 (mod n)
Soit n une puissance de deux. Alors 2 * n, 4 * n, 8 * n, etc., sont également des puissances de deux. Et en tant que somme de nombres consécutifs, ils ne sont pas représentables. Représentables sont 3 * n, 5 * n, 6 * n, 7 * n, 9 * n, etc. Celles. le nombre m * n doit avoir au moins un diviseur impair. Cependant, même le plus petit de ces multiples, 3 * n, doit être représenté par
(n - 1) + n + (n + 1).
Il n'y a pas d'autres représentations du nombre 3 * n. Car n en tant que puissance de deux n'a aucune représentation (voir l'instruction auxiliaire). Mais les termes de cette somme ne doivent pas dépasser le nombre n - 1. Par conséquent, 3 * n en tant que différence n'apparaîtra jamais. Pour les autres multiples, le raisonnement est exactement le même. Bien entendu, ni n ni 2 * n n'apparaîtront non plus comme des différences, comme des puissances de deux. Donc, toute puissance de deux est un nombre approprié.
La déclaration (1) est prouvée.
Maintenant, ne soyons pas une puissance de deux. Celles. représentable comme une somme de nombres consécutifs. La différence entre le premier et le dernier membre de la séquence (avant de prendre le module par n) sera:
d = 1 + 2 + 3 +… + (n-1).
Et les différences entre les membres de la séquence n-dial (avant de prendre le module) seront des sommes partielles de cette série. Si n est représentable comme une somme de nombres consécutifs, alors les plus grands nombres possibles qui composent une telle somme sont
[n / 2] et [n / 2] + 1. ([] est la partie entière d'un nombre)
Tous les autres les variantes d'une telle somme sont constituées de nombres encore plus petits ... Cela signifie que les membres de la séquence du cadran n, avec une différence avant de prendre le module égal à n, seront certainement trouvés. Et après avoir suivi le module, ils donneront les numéros correspondants. Celles. tout n qui n'est pas une puissance de deux, et donc représentable comme une somme de nombres consécutifs, n'est pas un nombre convenable.
La déclaration (2) est prouvée.
Au total, la tâche est complètement résolue. Les nombres appropriés sont toutes les puissances de deux et pas les autres. Vers la liberté en toute conscience !!!
La morale de cette fable n'en est peut-être qu'une. Les gars, même si vous faites des mathématiques pures, ne négligez pas les expériences informatiques. Oui, de telles expériences ne prouvent rien. Cependant, ils peuvent donner une estimation bien fondée. Bien que ce ne soit peut-être pas aussi simple qu'ici. Et prouver est généralement beaucoup plus facile que de deviner. Je serais heureux si quelqu'un trouvait cette présentation utile et intéressante.