Wir besitzen n Steine. Mit diesen bilden wir eine beliebige Anzahl von Häufchen, wobei jedes Häufchen aus <= l Steinen besteht (l ist eine Konstante). Ein besonderes Häufchen mit weniger als l Steinen bezeichen wir als ''Reserve''.
Ein Spielzug besteht aus zwei Schritten. Als erstes nehmen wir von jedem ''normalen'' Häufchen einen Stein und legen ihn in die Reserve. Dann bilden wir mit der Reserve neue Häufchen der Größe l, bis in der Reserve weniger als l Steine sind (es können auch 0 sein). Das wiederholen wir.
Es gibt in diesem Spiel nur eine endliche Anzahl von Zuständen. Daher muß jede Anfangskonfiguration irgendwann zyklisch werden.
Frage: Welche Länge haben die Grenzzyklen für l=255 und n=2008^2008+100*i mit i \in {0,1,2,3,4,5}?
1) Wann unterscheiden sich zwei Konfigurationen? Die "Reihenfolge" der normalen Häufchen ist irrelevant?
2) Die Startkonfiguration bei insgesmat n Steinen und der Konstanten l ist "n DIV l" normale Häufchen zu je l Steinen und dem Reserve-Haufen zu "n MOD l" Steinen?
3) Zählen z.B. für l=2 und n=3 folgende zwei Konfigurationen als verschieden:
a) ein normaler Haufen zu 2 Steinen und der Reserve-Haufen zu einem Stein,
b) ein normaler Haufen zu 1 Stein, ein normaler Haufen zu 2 Steinen und der Reserve-Haufen zu 0 Steinen?
Grüße,
Christian
p.s.: Die Aufgabe klingt recht interessant und zumindest auf den ersten blick nicht unbedingt einfach.
Buri
Senior Dabei seit: 02.08.2003 Mitteilungen: 46331
Herkunft: Dresden
Beitrag No.2, eingetragen 2008-03-20
Hi cyrix,
1. ja.
2. Diese Konfiguration ist eine der endlich vielen möglichen Konfigurationen, aber in der Aufgabe ist keine besondere Startkonfiguration ausgezeichnet, man kann aus jeder Stellung starten.
3. ja.
Gruß Buri
jobu0101
Ehemals Aktiv Dabei seit: 14.12.2006 Mitteilungen: 46
Beitrag No.3, eingetragen 2008-03-20
Man könnte sich ja ein Programm schreiben, das den Vorgang simuliert (das ist ja nicht so schwer). Nur die eigentliche Aufgabenstellung ließe sich damit natürlich aufgrund der großen Menge an Steinen nicht lösen ;)
trunx
Senior Dabei seit: 16.08.2003 Mitteilungen: 2867
Herkunft: Berlin
Beitrag No.4, eingetragen 2008-03-20
Hallo,
verstehe ich das richtig, dass nur am Anfang normale Häufchen der Größe < l gebildet werden können, dannach dürfen alle neuen normalen Häufchen nur noch die Größe l haben?
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.6, eingetragen 2008-03-20
Hab mich jetzt mal angemeldet nach langem passiven mitlesen, da mich die Aufgabenstellung auch etwas verwirrt. Das Argument, daß jede aus den Regeln gebildete Folge aus Zuständen zyklisch wird, stimmt zwar, aber die Länge des Zyklus wird doch im Normalfall vom Startzustand abhängen. Es soll also zu jedem Startzustand die Länge des Grenzzyklus angegeben werden?
HansHaas
Wenig Aktiv Dabei seit: 01.06.2007 Mitteilungen: 241
Herkunft: Straubing-Bogen (Bayern)
Beitrag No.7, eingetragen 2008-03-20
Hi Realshaggy,
ohne mir das genauer angesehen zu haben: Warum sollte die Länge der Zyklen vom Start abhängen? Mit der Bedingung, dass alle neuen Haufen nur l Steine haben dürfen, sind doch die mit anderer Steinanzahl irgendwann weg, es wäre also durchaus vorstellbar, dass alle Startkonfigurationen früher oder später in die gleich Situation münden.
Aber ich denke, den Rest der Diskussion sollten wir auf morgen vormittag verschieben
\EDIT: Das ist natürlich großer Mist, ist mir auch ca. 5 min. später aufgefallen. Allerdings war da der PC schon aus.
Gruß,
Hans
[ Nachricht wurde editiert von HansHaas am 20.03.2008 20:42:01 ]
ZetaX
Senior Dabei seit: 24.01.2005 Mitteilungen: 2804
Herkunft: Wenzenbach
Beitrag No.8, eingetragen 2008-03-20
Ich bin zwar nicht Aufgabensteller, aber ja, die späteren Haufen dürfen beim Erstellen nur exakt die Größe l haben. Andernfalls würde das ganze auch nicht zyklisch werden müssen (man kann dann nichtzyklische Zugfolgen angeben). Das ganze ist nach Wahl der Startaufstellung also determiniert.
Dass alle Startzustände wohl gleich lange Grenzzyklen haben wird aber in der Tat von der Aufgabenstellung etwas vorweggenommen, ohne dort bereits begründet zu sein
Buri
Senior Dabei seit: 02.08.2003 Mitteilungen: 46331
Herkunft: Dresden
Beitrag No.9, eingetragen 2008-03-20
2008-03-20 18:03 - HansHaas schreibt:
... sind doch die mit anderer Steinanzahl irgendwann weg ...
Hi HansHaas,
nein, schau noch einmal in die Aufgabe.
@Realshaggy
willkommen im Forum!
Es stimmt, die Aufgabenformulierung setzt etwas voraus, was man noch nicht wissen kann. Im Moment darf man aber nicht mehr dazu sagen.
Gruß Buri
cow_gone_mad
Senior Dabei seit: 11.01.2004 Mitteilungen: 6651
Beitrag No.10, eingetragen 2008-03-21
Hallo ihr
Beginnen wir mal. Aber noch mit Vorsicht zu geniessen...
\ Lemma. Das System mit n Steinen hat gleich lange Endzyklen wie das System mit m = n (mod l(l+1)/2) Steinen.
Beweisskizze: Sei k = 2 (n - m)/(l(l+1)). Jetzt veraendere man ein System mit m Steinen so, dass man fuer jedes 1 \leq j \leq l jeweils k Haufen mit j Steinen hinzufuegt. Man kann nun nachrechnen, dass die Zyklen laenge gleich bleibt. Was den Beweis mit Vorbehalten von Rechen- / Denkfehlern beendet.
Realshaggy
Senior Dabei seit: 20.03.2008 Mitteilungen: 1293
Beitrag No.11, eingetragen 2008-03-21
Habe mit folgender Modellierung über Zahlenfolgen gearbeitet, aber bis jetzt nicht viel weitergekommen.
Die Startkonfiguration ist beschrieben durch l Zahlen a_1,...,a_l, wobei a_k die Anzahl der Häufchen mit genau k Steinen beschreibt.
Der Rest ist
r= n - summe(k a_k,k=1,k=l)
Der erste Schritt läßt sich folgendermaßen beschreiben:
Bilde a_(l+1) gemäß
a_(l+1)= (r + sum(a_k,k=1,k=l)) div l
und betrachte die Zahlen a_2,...,a_(l+1). Jetzt beschreibt a_2 die Anzahl der Haufen mit genau einem Stein usw. oder allgemein a_k die Anzahl der Haufen mit genau k-1 Stein.
Dieses Verfahren läßt sich fortsetzen, allgemein ergibt sich
a_(j+1)= ( n - summe( a_k ( l-j+k+1), k=j-l+1,j)) div l
Insgesamt erhält man so eine Zahlenfolge und es genügt, die kleinste Periode der Zahlenfolge zu bestimmen.
Die erste Spalte ist der Reserve-Haufen.
Die markierte Zeile gibt das erstmalige Auftreten der letzten Zeile an.
Da die Anfangsverteilung auf die Haufen keine Rolle spielt (was noch zu beweisen wäre), kann man auch einfach so verteilen: Reserve L-1 Steine, dann jeweils L und zum Schluß den Rest <L.
Nach jedem Schritt werden die Häufchen absteigend sortiert, was die Wiedererkennung einer Konfiguration erleichtert. Deswegen steht auch in der 2. Zeile gleich die 22 vorne dran, weil der Reservehaufen neu verteilt wurde.
viertel
Senior Dabei seit: 04.03.2003 Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.13, eingetragen 2008-03-21
Ich hab mal die Zyklenlängen für verschiedene N und L Kombinationen ermittelt. Für N<L macht es nicht viel Sinn, erst für N≥L. Und so ist die Kopfzeile für N auch als Offset zu L zu verstehen. Z.B. die 2 Zelle F4 wurde für L=5 und N=L+4=9 berechnet.
Die Farben machen nur die Struktur der gleichen Zyklenlängen besser sichtbar.
Dies ist nur ein kleiner Ausschnitt. Einmal draufklicken, und es gibt ein richtig großes Bild (154KB, das wegen seiner Größe leider nicht auf dem MP liegt).
Hast Du ne Idee?
Aber frag bitte nicht, ob das N der Aufgabenstellung auch geht
EDIT
Hoppla, mit Deinem Lemma aus Beitrag 10 wären wir damit dann fertig.
Müßte also noch das Lemma verifiziert werden. Bin leider nicht so der Zahlentheoretiker, eher der Programmierer. Aber damit könnte man zumindest die Idee für kleinere N verifizieren.
[ Nachricht wurde editiert von viertel am 21.03.2008 16:30:38 ]
cow_gone_mad
Senior Dabei seit: 11.01.2004 Mitteilungen: 6651
Beitrag No.16, eingetragen 2008-03-21
Naja, die Idee steht oben, aber nicht sehr verstaendlich.
Idee 1: Wenn du l(l + 1)/2 Steine hast, kannst du sie so plazieren, dass sie 1 zyklisch sind, und die Reserve immer leer. Einfach in dem man einen Haufen mit einem Stein, einen mit 2, einem mit 3, usw... bis einen mit l macht. Man bekommt, weil man l Haufen hat, immer den l-ten Haufen dazu.
Idee 2: Wenn du zu einem System mit N Steinen, das periodisch ist, l(l+1)/2 in oben genannter Art addierst, bleibt es periodisch mit gleicher Periode.
Und Mathematica sagt halt 2008^2008 (mod 255 * 256/2) = 256.
Der Vollstaendigkeit wegen fehlt noch ein Beweis, dass Grenzzyklen immer die gleiche Laenge haben. Und vielleicht ausformulierte Beweise. Aber alles mit der Zeit...
@1/4: Kannst du die Grenzkonfigurationen ausgeben? Ich bin nur neugierig...
viertel
Senior Dabei seit: 04.03.2003 Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.20, eingetragen 2008-03-22
Es gibt nicht die Grenzkonfiguration. Wie der Zyklus abläuft hängt von der Anfangskonfiguration ab. Hier noch mal ein Lauf wie oben, aber mit anderer Anfangsverteilung (der Punkt vor der 9 verhindert nur, daß diese Zeile um eine Stelle nach links rutscht):
Interessanterweise ist es aber der gleiche Zyklus, nur verschoben.
Nochmal, wieder anderer Start, aber hier ist der Zyklus der gleiche wie in Beitrag 12, aber vergleiche mal die 2 Konfigurationen vor dem Eintritt in den Zyklus:
cow_gone_mad
Senior Dabei seit: 11.01.2004 Mitteilungen: 6651
Beitrag No.21, eingetragen 2008-03-23
2008-03-22 04:30 - viertel schreibt:
Es gibt nicht die Grenzkonfiguration.
Oh. Das macht das Beweisen, dass alle Grenzzklen gleiche Laenge haben. Schwieriger ... Allerdings kann man eine beliebige Grenzkonfiguration erzwingen, in dem man die Steine in diese setzt!
\ Ich beginne mal mit dem Formalisieren. Wir bezeichen mit N die Anzahl der Steine. Mit r die Anzahl der Steine in der Reserve und mit a_i, i =1 ,..., l die Anzahl der Haufen der Groesse i.
Wir schreiben r(t), a_i(t) fuer die Anzahl zur Zeit t \in \IN.
Jetzt nochmal mein Lemma. \big\ Lemma \normal\ Sei b_i(t) eine Konfiguration, so dass die zugehoerige Reserve leer ist, sowie b_i(t +1) = b_i(t). Sei a_i(t), r(t) eine andere Konfiguration. Dann gilt a_i(t) + b_i(t), r(t) ist auch eine Konfiguration.
\big\ Beweis \normal\ Wir muessen zeigen, dass gilt a_i(t + 1) + b_i(t + 1) = a_(i+1)(t) + b_(i+1)(t) fuer i = 1,..., l-1. r(t+1) = sum((a_i(t) + b_i(t)),i=1,l) + r(t) (mod l) = sum((a_i(t)),i=1,l) + r(t) + sum(b_i(t),i=1,l) (mod l) a_l(t+1) + b_l(t+1) = sum(a_i(t) + b_i(t),i=1,l) + r(t) (div l) Das ist aber klar, da alles additiv ist, z.b. ist nach annahme sum(b_i(t),i=1,l) (mod l) = 0, was die zweite Gleichheit zeigt. \big\ q.e.d. \normal\
Man prueft leicht nach, dass b_i(t) = 1, i = 1, ..., l eine Konfiguration mit l (l +1)/2 Steinen ist.
Also kann man sich oben auf die Anzahl der Steine modulo 255 * 128 einschraenken.
Das hilft zwar noch nicht fuer die Frage der Konstanz der Laenge der Grenzzyklen. Ist aber sauberer als was da stand.
Liebe Gruesse,
cow_
[ Nachricht wurde editiert von fed am 23.03.2008 01:28:30 ]
Florian
Senior Dabei seit: 25.10.2004 Mitteilungen: 893
Herkunft: Salzburg, Österreich
Beitrag No.22, eingetragen 2008-03-23
@viertel:
Wenn ich nicht zu sehr ablenke hätte es mich interessiert wie lange dein Programm gebraucht hat um L=255 uns N=656 zu berechnen. Schluckt es auch L=255 und N=4256?
Lg Flo
Ps: Es gibt noch unentdeckte Muster in der Aufgabe :-)
cow_gone_mad
Senior Dabei seit: 11.01.2004 Mitteilungen: 6651
Beitrag No.23, eingetragen 2008-03-23
2008-03-23 02:30 - Florian schreibt:
Ps: Es gibt noch unentdeckte Muster in der Aufgabe
Ja, zum Beispiel gilt fuer jedes a_i \leq floor(N/l). Aber ich weiss nicht wie man das sinnvoll einbauen kann.
Aber ich vermute, dass es eine Theorie fuer solche Spiele geben sollte. Man koennte Kanonen auffahren, und mit allgemeiner Theorie zuschlagen. Aber mir faellt da nichts hilfreiches ein ... (Meine Raeume sind immer deutlich groesser ...)
viertel
Senior Dabei seit: 04.03.2003 Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.24, eingetragen 2008-03-23
2008-03-23 02:30 - Florian schreibt:
@viertel:
Wenn ich nicht zu sehr ablenke hätte es mich interessiert wie lange dein Programm gebraucht hat um L=255 uns N=656 zu berechnen. Schluckt es auch L=255 und N=4256?
Das geht in Sekundenbruchteilen. Allerdings sind historisch noch ein paar Umständlichkeiten drin. Deswegen schluckt es im Moment auch noch nicht N=4256. Bei wachsendem N wird aber anscheinend auch die Vorperiode immer länger. Auch das müßte ich dann ändern, daß der Priodenanfang vom Ende her gesucht wird. Denn die Periode ist deutlich kürzer als die Vorperiode.
Blöderweise kann meine Compiler-IDE nur ein Projekt zu einer Zeit offen haben. Und ich arbeite gerade an was anderem, so daß ein Ändern dieses Programms hier umständlich wäre.
Florian
Senior Dabei seit: 25.10.2004 Mitteilungen: 893
Herkunft: Salzburg, Österreich
Beitrag No.25, eingetragen 2008-03-29
Lösung:
Eure Lösung stimmt. Da in der Aufgabe einiges verborgen ist (und wenig bewiesen) werde ich in den nächsten Tagen einen Artikel schreiben der sie ausführlich behandelt. Das in der Aufgabe beschriebene Spiel ist übrigen unter dem Namen "Austrian Solitaire" bekannt.