Leute, erwartet keine herausragenden mathematischen Schönheiten oder nützlichen Algorithmen im Leben. Ich schreibe nur aus rein sportlichem Interesse. Ich interessierte mich für das hier veröffentlichte Problem , mit dem amerikanische Gefangene ihre riesigen Strafen vertreiben. Nach den Kommentaren zum Artikel zu urteilen, hat es bereits ein gewisses Interesse an der Community geweckt. Ich verstehe, dass es mir nicht sehr gut geht, ich hätte den Leuten Zeit geben sollen, selbst nachzudenken. Ich bereue jedoch, ich bin ein Sünder, ich kann nicht widerstehen. Und ich poste meine Entscheidung hier. Wen kümmert es, willkommen bei Katze. Wenn Sie selbst etwas mehr nachdenken möchten, lesen Sie es noch nicht.
Also die Aufgabe selbst. Ich werde es etwas klarer formulieren als im Artikel selbst (leider ist die Übersetzung dort etwas schief).
Das Einstellrad (wie in Abbildung 1) kann auf eine beliebige Ganzzahl von 1 bis n zeigen, wenn es gegen den Uhrzeigersinn gedreht wird. Der Countdown beginnt bei 1, dann dreht sich der Pfeil nacheinander (immer gegen den Uhrzeigersinn) um eine Position, dann um zwei, dann um drei usw. bis zur letzten Umdrehung um n-1 Position. Wir sammeln die Reihenfolge aller Zahlen, auf die der Pfeil zeigt.
Wenn beispielsweise n = 12 ist, erhalten Sie die Sequenz 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Es ist ersichtlich, dass sich darin wiederholte Zahlen befinden.
Und für n = 8 ist die Folge 1, 2, 4, 7, 3, 8, 6, 5. Und es gibt keine sich wiederholenden Zahlen.
Die Frage ist, für welche Werte von n werden die Zahlen in der Sequenz nicht wiederholt?
Präsentiert von Gary Gordon und Denise Ozbay, November 2020, Mathematical Horizons.
Nennen wir die Sequenz, die im Problem aufgebaut ist, die Sequenz des n-Zifferblatts . Und Zahlen, n , für die diese Sequenz enthält keine Zahlen zu wiederholen, sind geeignet .
Beginnen wir mit einem sehr ernsten Tipp. Fast sofort fertige Antwort. Ich bin nicht in amerikanische Gefängnisse gegangen und weiß nicht, ob den Insassen dort Computer zur Verfügung stehen. Aber ich habe mein Kriegspferd auf meinem Tisch! Es ist also eine Sünde, es nicht zu benutzen. Wir starten unser Lieblings-Jupyter-Notizbuch und geben ein kleines Programm ein:
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
Wenn Sie getList (12345) ausführen, erhalten Sie eine Liste mit 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192. Es ist
also sehr wahrscheinlich, dass nur Zweierpotenzen gültige Zahlen sind. und sonst nichts. Es bleibt nur zu beweisen. Genauer gesagt müssen zwei Aussagen bewiesen werden:
1) Jede Zweierpotenz ist eine geeignete Zahl.
2) Eine Zahl, die keine Zweierpotenz ist, ist nicht geeignet.
Lassen Sie uns zunächst sehen, woher die sich wiederholenden Nummern in der n-Dial-Sequenz stammen.
Die Sequenz beginnt bei 1. Ihr Inkrement im ersten Schritt ist ebenfalls gleich 1 und erhöht sich dann mit jedem Schritt um 1. Der Rest der Division durch n wird als Ergebnis genommen. Wenn der Rest Null ist, wird außerdem angenommen, dass das Ergebnis gleich n ist. Versuchen wir, eine solche Sequenz für eine nicht sehr große Zahl n zu konstruieren. Zum Beispiel 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
Wir sehen, dass zwei Paare zusammenfielen: s (1) und s (4) und s (3) und s (6). Wenn wir die Werte nicht modulo nehmen, ist der Unterschied zwischen den größeren und kleineren Elementen beider Paare ein Vielfaches von 6. Das ist im Allgemeinen durchaus verständlich. Der Endwert wird modulo n genommen. Und wenn sich die Zahlen vor der Verwendung des Moduls um n (oder ein Vielfaches von n) unterscheiden, stimmen die Endwerte überein.
Andererseits, da das Inkrement, das wir bei jedem Schritt haben, um 1 zunimmt. Und es ist klar, dass die obigen Unterschiede gleich den Summen einiger aufeinanderfolgender Zahlen sind. Zum Beispiel für das Paar s (1), s (4):
7 = 1 + (1 + 2 + 3)
und für das Paar s (3), s (6):
16 = 4 + (3 + 4 +) 5)
Für das erste beträgt der Unterschied 6 für das Paar und 12 für das zweite.
Somit kommen wir zu einer wichtigen Schlussfolgerung:
Wenn übereinstimmende Zahlen in der Folge des n-Zifferblatts erscheinen, kann n oder sein Vielfaches als Summe einiger aufeinanderfolgender Zahlen dargestellt werden, von denen die größte die Zahl n-1 nicht überschreitet.
Zunächst beweisen wir eine Hilfsaussage:
Jede Zahl, die keine Zweierpotenz ist, kann als Summe aufeinanderfolgender Zahlen dargestellt werden. Keine Zweierpotenz kann durch die Summe aufeinanderfolgender Zahlen dargestellt werden.
Lassen Sie uns darüber nachdenken, wie eine Zahl im Allgemeinen als Summe aufeinanderfolgender Zahlen dargestellt werden kann. Für die Ungeraden ist das ganz einfach. Wenn A ungerade ist, kann es durch ein Paar dargestellt werden:
A = [A / 2] + ([A / 2] + 1), wobei [] den ganzzahligen Teil der Zahl bedeutet.
Zum Beispiel 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
Es ist nur das für Vielfache von 3. Wenn A ein Vielfaches von 3 ist, dann gilt:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
In ähnlicher Weise, wenn A ein Vielfaches von 5 ist:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
Und wenn die Zahl A einen ungeraden Teiler B hat, kann sie im Allgemeinen als Summe von B aufeinanderfolgenden Zahlen dargestellt werden, und die Zahl A / B liegt genau in der Mitte.
Beispiele:
27 = 3 * 9. Daher ist 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10,50
= 5 * 10. Daher ist 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
Das Gegenteil ist ebenfalls offensichtlich. Wenn eine Zahl als Summe einer ungeraden Anzahl aufeinanderfolgender Zahlen darstellbar ist, hat sie einen ungeraden Teiler, und die Darstellung selbst hat die oben beschriebene Form. Daher kann die Zweierpotenz nicht die Summe einer ungeraden Anzahl aufeinanderfolgender Zahlen sein , da sie keine ungeraden Teiler hat.
Aber was ist mit der Summe einer geraden Anzahl aufeinanderfolgender Zahlen? Die Summe zweier aufeinanderfolgender Zahlen ist immer ungerade. Das ist hoffentlich offensichtlich. Die Summe von vier kann als die Summe von zwei Paaren betrachtet werden, von denen jedes ungerade ist. Die Summe von vier ist also gerade. Die Summe von sechs ist wieder ungerade, die Summe von acht ist gerade und so weiter. Jene. Die Summe einer geraden Anzahl aufeinanderfolgender Zahlen ist gerade, wenn ihre Zahl ein Vielfaches von 4 ist, und ungerade, wenn es ein Vielfaches von nur 2 ist.
Eine gerade Zahl A sei die Summe von 4 * k aufeinanderfolgenden Zahlen. Der Einfachheit halber sei k = 1, für großes k ist die Argumentation völlig analog:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Teilen Sie diese Gleichheit durch 2 :
A / 2 = (4 · a + 6) / 2 = 2 · a + 3 = (a + 1) + (a + 2).
Jene. wieder erhalten wir die Summe der fortlaufenden Zahlen.
Daher , wenn eine gerade Zahl A eine Darstellung in Form der Summe einer geraden Anzahl von aufeinanderfolgenden Zahlen ist, dann einige Darstellung in Form einer Summe von aufeinanderfolgenden Zahlen besteht für A / 2 .
Zum Beispiel:
26 = 5 + 6 + 7 + 8. Daher ist 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Angenommen, für die N-te Potenz von zwei gibt es eine Darstellung in Form einer Summe einer geraden Anzahl aufeinanderfolgender Zahlen (es gibt keine Darstellung in Form einer ungeraden Zahl dafür, wie oben gezeigt). Dann gibt es eine Darstellung in Form einer Summe aufeinanderfolgender Zahlen für den Grad N-1. Und die Anzahl der darin enthaltenen Begriffe ist auch gerade. Durch Induktion kann das Gleiche über den Grad N-2 und über den Grad N-3 und im Allgemeinen über jeden Grad kleiner als N gesagt werden. Es gibt jedoch keine Darstellung in Form einer Summe aufeinanderfolgender Zahlen für die Zahl 4, was leicht zu sehen ist. Daher kann keine Zweierpotenz als Summe aufeinanderfolgender Zahlen dargestellt werden .
Andererseits kann jede Zahl, die keine Zweierpotenz ist, als Summe aufeinanderfolgender Zahlen dargestellt werden. Wenn diese Zahl ungerade ist, kann sie als Paar dargestellt werden. Wenn es gerade und keine Zweierpotenz ist, hat es mindestens einen ungeraden Teiler. Und dadurch darstellbar.
Die Hilfsaussage ist bewiesen.
Betrachten Sie die gesamte n-Dial-Sequenz.
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)
Sei n eine Zweierpotenz. Dann sind 2 * n, 4 * n, 8 * n usw. ebenfalls Zweierpotenzen. Und als Summe aufeinanderfolgender Zahlen sind sie nicht darstellbar. Darstellbar sind 3 * n, 5 * n, 6 * n, 7 * n, 9 * n usw. Jene. Die Zahl m * n muss mindestens einen ungeraden Teiler haben. Selbst das kleinste dieser Vielfachen, 3 * n, muss jedoch als
(n - 1) + n + (n + 1) dargestellt werden.
Es gibt keine anderen Darstellungen der Zahl 3 * n. Denn n als Zweierpotenz hat überhaupt keine Repräsentation (siehe Hilfsaussage). Die Terme in dieser Summe sollten jedoch die Zahl n - 1 nicht überschreiten. Daher wird 3 * n als Differenz niemals auftreten. Für andere Vielfache ist die Argumentation genau dieselbe. Natürlich erscheinen weder n noch 2 * n als Unterschiede, als Zweierpotenzen. Jede Zweierpotenz ist also eine geeignete Zahl.
Aussage (1) ist bewiesen.
Nun sei n keine Zweierpotenz. Jene. darstellbar als Summe aufeinanderfolgender Zahlen. Der Unterschied zwischen dem ersten und dem letzten Mitglied der Sequenz (bevor das Modul um n genommen wird) beträgt:
d = 1 + 2 + 3 +… + (n-1).
Und die Unterschiede zwischen den Mitgliedern der n-Dial-Sequenz (vor der Aufnahme des Moduls) sind Teilbeträge dieser Serie. Wenn n als Summe aufeinanderfolgender Zahlen darstellbar ist, sind die größtmöglichen Zahlen, aus denen eine solche Summe besteht,
[n / 2] und [n / 2] + 1. ([] ist der ganzzahlige Teil einer Zahl)
Alle anderen Varianten einer solchen Summe bestehen aus noch kleineren Zahlen ... Dies bedeutet, dass die Elemente der Sequenz des n-Zifferblatts mit einem Unterschied vor der Annahme des Moduls gleich n mit Sicherheit gefunden werden. Und nachdem sie das Modul genommen haben, geben sie die passenden Nummern an. Jene. Jedes n, das keine Zweierpotenz ist und daher als Summe aufeinanderfolgender Zahlen dargestellt werden kann, ist keine geeignete Zahl.
Aussage (2) ist bewiesen.
Insgesamt ist die Aufgabe vollständig gelöst. Geeignete Zahlen sind beliebige Zweierpotenzen und keine anderen. Mit gutem Gewissen in die Freiheit !!!
Die Moral dieser Fabel ist vielleicht nur eine. Leute, auch wenn ihr reine Mathematik macht, vernachlässigt Computerexperimente nicht. Ja, solche Experimente beweisen nichts. Sie können jedoch eine fundierte Vermutung anstellen. Obwohl es vielleicht nicht so einfach ist wie hier. Und das Beweisen ist normalerweise viel einfacher als das Erraten. Ich würde mich freuen, wenn jemand diese Präsentation nützlich und interessant finden würde.