Rechenaufgaben

[kad]

In dem alten buddhistischen Kloster Wan-Dan (nahe Hanoi) beschäftigen sich die Mönche seit alters her mit einem heiligen Brauch:
Sie haben 2000 Edelsteine zur Verfügung, die sich alle voneinander unterscheiden. Zu Beginn des Ritus wird an einem Morgen eine gerade Anzahl 2n von Steinen ausgewählt. Sodann werden, um zugleich die Vielfältigkeit und die Ausgewogenheit der Welt zu versinnbildlichen, die 2n Steine in andächtiger Ruhe dreimal täglich, am Morgen, am Mittag und am Abend, auf eine kupferne und eine irdene Schale aufgeteilt, und zwar so, dass in jede Schale n Steine kommen.
Hierbei wird strengstens darauf geachtet, dass jede mögliche Verteilung der Steine auf die beiden Schalen im Laufe des Rituals genau einmal vorkommt. Für die Zukunft des Klosters ist nun entscheidend, wann das Ende des Rituals erreicht wird: Geschieht es des Abends, so verheißt die Zukunft Gutes. Ansonsten aber droht schweres Unheil.
Für wie viele Zahlen 2n an gewählten Edelsteinen mit 1 ≤ n ≤ 1000 können die Mönche beruhigt in die Zukunft blicken?

Spoiler

Ritual beginnt mit:
Am ersten Morgen legt man fest wieviele (=2n) bit (maximal 2.000) die binäre Zahl für dieses Ritual haben soll.
Davon wird die Hälfte der bit auf 1 gesetzt (irdene Schale) und die andere Hälfte auf 0 belassen (kupferne Schale)
Täglich wird nun:
Morgens (mit Ausnahme des ersten Tages) werden mo bit von 1 auf 0 und mo bit von 0 auf 1 gesetzt (Steine wechseln die Schalen)
Mittags werden mi bit von 1 auf 0 und mi bit von 0 auf 1 gesetzt (Steine wechseln die Schalen)
Abends werden a bit von 1 auf 0 und a bit von 0 auf 1 gesetzt,
wobei immer darauf geachtet wird, dass dies nicht einer Verteilung (Zahl) entspricht, die seit Beginn des Rituals schon mal erreicht wurde.
Dies so lange bis keine neue Zahl mehr gebildet werden kann.

Mit n=1 wären nur 2 Steine im Spiel und das würde zwangsweise dazuführen, dass schon am ersten Abend
wieder der Zustand vom Morgen erreicht wird.
Morgens: 01
Mittags: 10
Abends: 01

Jetzt ist ein bisschen die Frage, ob das Ritual in obigem Falle Mittags endet (Fall 1: letzte neue Zahl)
oder Abends (Fall 2: keine neue Zahl mehr möglich).

Offensichtlich gibts wegen der gleichvielen 0en und 1en genau 2^n mögliche Zahlen, die in dieser Reihenfolge gelegt werden:
(mo,mi,ab)
1,2,3
4,5,6
7,8,9
....

Im Fall 1 (das Ritual endet mit der letzten neuen Zahl) endet das Ritual nie am Abend, da 2^n nicht durch drei teilbar ist.

Im Fall 2 (das Ritual endet mit der ersten bereits gelegten Zahl) also mit 2^n+1.

Von diesen ist jede Zweite durch drei teilbar (2^1, 2^3, 2^5...)
Damit sind die "günstigen" n = alle ungeraden Zahlen < 1000
und die zugehörigen 2n die geraden Zahlen < 2000.
Das wären dann 500 verschieden n (bzw. 2n) von 1000 möglichen.

Wenn mich nicht alles täuscht, enden die anderen Rituale immer Mittags und nie an einem Morgen.
Kurios.

Spoiler

Zu

Mit n=1 wären nur 2 Steine im Spiel und das würde zwangsweise dazuführen, dass schon am ersten Abend
wieder der Zustand vom Morgen erreicht wird.
Morgens: 01
Mittags: 10
Abends: 01

Jetzt ist ein bisschen die Frage, ob das Ritual in obigem Falle Mittags endet (Fall 1: letzte neue Zahl)
oder Abends (Fall 2: keine neue Zahl mehr möglich).

Hier endet das Ritual am Mittag. „Letzte neue Zahl.“
Man sieht übrigens, dass für n=2 das Ritual am Abend endet.

Dein Resultat für den Fall 1 ist jedoch noch nicht richtig. Wieso 2^n?
Der Test mit „durch 3 teilbar“ ist natürlich der richtige Ansatz.
(n=2 endet am Abend)

Ich mach mal hier weiter:

Spoiler

Analaog zu den 2n Steinen kann man sich eine Binärzahl vorstellen.
0->(kupferne Schale)
1->(irdene Schale)
Diese Zahl kann man in zwei Hälften der Länge n teilen.
für den linken Teil gibts dann 2^n Möglichkeiten.
Der Rechte entsteht aus Invertierung der linken Hälfte.
Damit haben wir immer gleich viele Steine in jeder Schale.

In meinem ersten Lösungsansatz hatte ich jedoch übersehen, dass es
zu jeder Bitkombination links, rechts nicht nur eine sondern mehrere passende Kombinationen bzw. eindeutige Permutationen geben kann.
Also schauen wir uns die linke noch mal genauer an.
sind links nur 0'en, sind rechts nur 1'en -> 1 Möglichkeit
ist links genau eine 1 (n Möglichkeiten) ist rechts genau eine 0 (n Möglichkeiten) -> n²
sind links genau 2 1en (n*(n-1) Möglichkeiten) gilt dies auch für die 0 rechts -> (n*(n-1))²
....
ist links genau eine 0 (n Möglichkeiten) ist rechts genau eine 1 (n Möglichkeiten) -> n²
sind links nur 1'en, sind rechts nur 0'en -> 1 Möglichkeit

Damit haben wir Binomialkoeffizienten zum Quadrat, also
n=1-> 1²+1² =2 (Rest Mod3 2)
n=2-> 1²+2²+1² = 6 (Rest Mod3 0)
n=3-> 1²+3²+3²+1² = 20 (Rest Mod3 2)
n=4-> 1²+4²+6²+4²+1² =70 (Rest Mod3 1)

Damit ist die Anzahl der möglichen Kombinationen für gegebenes n = Summe (k=0 bis n) (n!/(k!*(n-k)!)²

Jetzt ist nur noch zu klären, für welche n, diese Anzahl durch 3 teilbar ist.

Schauen wir uns mal einige Zahlen an:
n/Anzahl/Rest Mod3
1/2/2
2/6/0
3/20/2
4/70/1
5/252/0
6/924/0
7/3.432/0
8/12.870/0
9/48.620/2
10/184.756/1
11/705.432/0
12/2.704.156/1
13/10.400.600/2
14/40.116.600/0
15/155.117.520/0
16/601.080.390/0
17/2.333.606.220/0
18/9.075.135.300/0
19/35.345.263.800/0
20/137.846.528.820/0

Wenn ich mit diesem Lösungsansatz nicht völlig daneben liege, wären das bei n=20 schon 137.846.528.820 verschiedene Kombinationen.
Ob die letzte davon dann am Abend gelegt wird, würde man erst in 125.887.241 Jahren erfahren.

Zurück zum Rätsel.
Diese Anzahl ist natürlich die Summe über die Diagonale der Wahrscheinlichkeitsmatrix die bei einem früheren Rätsel schon mal vorkam.
Da hatten wir (a+b)^n * (a+b)^(n+1)

Diese Zahlen bis n=1000 zu berechnen ist ziemlich sinnfrei.
Also muss die Modulo Opteration wohl früher eingesetzt werden und ev. ausgehend von der Teilbarkeit von n auf n+1 geschlossen werden können.

tbc.

Spoiler

Die Anzahl der möglichen Kombinationen stimmt. Ich habe aber direkt „2n über n“ genommen (auf wieviele Arten kann ich n Edelsteine aus 2n Edelsteinen auswählen.

Wann ist „2n über n“ durch 3 teilbar?

Ja, schon bei n=20 gibt es grosse Zahlen (wobei mit Schaltjahren die Zahl etwas kleiner wird )

Ein Ansatz wäre, sich zu überlegen, mit welcher Vielfachheit 3 in n! vorkommt. Aber es gibt dann noch einiges zu tun.

[giffi marauder]

Spoiler

Die Anzahl der möglichen Kombinationen stimmt. Ich habe aber direkt „2n über n“ genommen (auf wieviele Arten kann ich n Edelsteine aus 2n Edelsteinen auswählen.

Wann ist „2n über n“ durch 3 teilbar?

Ja, schon bei n=20 gibt es grosse Zahlen (wobei mit Schaltjahren die Zahl etwas kleiner wird )

Ein Ansatz wäre, sich zu überlegen, mit welcher Vielfachheit 3 in n! vorkommt. Aber es gibt dann noch einiges zu tun.

Spoiler

Na das ist dann doch ein bisschen handlicher.
2n über n ist dann (2n)!/(n!*n!)
-> (n+1)*...*2n / n!
Diese Zahl ist genau dann durch drei teilbar, wenn die Potenz von 3 in der Primfaktorzerlegung von (n+1)*(n+2)...*2n
größer als die Potenz von 3 in der Primfaktorzerlegung von n! ist.
P(n) wäre dann n/3+n/3^2+n/3^3+n/3^4+n/3^5 (ganzahlige Division)
P(2n) wäre dann 2n/3+2n/3^2+2n/3^3+2n/3^4+2n/3^5+2n/3^6 (ganzahlige Division)
und wenn 2*P(n)<P(2n) dann ist die Anzahl durch 3 teilbar und der Zyklus endet am Abend.

[kad]

Spoiler

Die Anzahl der möglichen Kombinationen stimmt. Ich habe aber direkt „2n über n“ genommen (auf wieviele Arten kann ich n Edelsteine aus 2n Edelsteinen auswählen.

Wann ist „2n über n“ durch 3 teilbar?

Ja, schon bei n=20 gibt es grosse Zahlen (wobei mit Schaltjahren die Zahl etwas kleiner wird )

Ein Ansatz wäre, sich zu überlegen, mit welcher Vielfachheit 3 in n! vorkommt. Aber es gibt dann noch einiges zu tun.

Spoiler

Na das ist dann doch ein bisschen handlicher.
2n über n ist dann (2n)!/(n!*n!)
-> (n+1)*...*2n / n!
Diese Zahl ist genau dann durch drei teilbar, wenn die Potenz von 3 in der Primfaktorzerlegung von (n+1)*(n+2)...*2n
größer als die Potenz von 3 in der Primfaktorzerlegung von n! ist.
P(n) wäre dann n/3+n/3^2+n/3^3+n/3^4+n/3^5 (ganzahlige Division)
P(2n) wäre dann 2n/3+2n/3^2+2n/3^3+2n/3^4+2n/3^5+2n/3^6 (ganzahlige Division)
und wenn 2*P(n)<P(2n) dann ist die Anzahl durch 3 teilbar und der Zyklus endet am Abend.

Spoiler

Das ist der richtige Weg, aber es gibt noch zu tun….
Und es geht ohne gross zu rechnen.

Asteroid Helio gibt die Anzahl. Aber das hilft nicht so….

[giffi marauder]

[/Spoiler]

Spoiler

Die Anzahl der möglichen Kombinationen stimmt. Ich habe aber direkt „2n über n“ genommen (auf wieviele Arten kann ich n Edelsteine aus 2n Edelsteinen auswählen.

Wann ist „2n über n“ durch 3 teilbar?

Ja, schon bei n=20 gibt es grosse Zahlen (wobei mit Schaltjahren die Zahl etwas kleiner wird )

Ein Ansatz wäre, sich zu überlegen, mit welcher Vielfachheit 3 in n! vorkommt. Aber es gibt dann noch einiges zu tun.

Spoiler

Na das ist dann doch ein bisschen handlicher.
2n über n ist dann (2n)!/(n!*n!)
-> (n+1)*...*2n / n!
Diese Zahl ist genau dann durch drei teilbar, wenn die Potenz von 3 in der Primfaktorzerlegung von (n+1)*(n+2)...*2n
größer als die Potenz von 3 in der Primfaktorzerlegung von n! ist.
P(n) wäre dann n/3+n/3^2+n/3^3+n/3^4+n/3^5 (ganzahlige Division)
P(2n) wäre dann 2n/3+2n/3^2+2n/3^3+2n/3^4+2n/3^5+2n/3^6 (ganzahlige Division)
und wenn 2*P(n)<P(2n) dann ist die Anzahl durch 3 teilbar und der Zyklus endet am Abend.

Spoiler

Das ist der richtige Weg, aber es gibt noch zu tun….
Und es geht ohne gross zu rechnen.

Asteroid Helio gibt die Anzahl. Aber das hilft nicht so….

Spoiler

Kleiner Ausflug:
Giffi: Damit ist die Anzahl der möglichen Kombinationen für gegebenes n = Summe (k=0 bis n) (n!/(k!*(n-k)!)²
Kad: Ich habe aber direkt „2n über n“ genommen (auf wieviele Arten kann ich n Edelsteine aus 2n Edelsteinen auswählen.
Diese Gleichheit hat sogar einen Namen:
Vandermondesche Identität
https://de.wikipedia.org/wiki/Mittlerer ... oeffizient

Unbenannt.png (14.25 KiB) 529 mal betrachtet

[kad]

Ein Rätsel für alle.

Bestimme den Umfang

287DA547-85B6-48C9-AFC7-4360D757D291.jpeg (10.9 KiB) 481 mal betrachtet

[giffi marauder]

Ein Rätsel für alle.

Bestimme den Umfang

287DA547-85B6-48C9-AFC7-4360D757D291.jpeg

Spoiler

Der Umfang ist 42.
2*(9+12)
Dass wir zischendurch schon mal ein Stück (s) zurücklaufen, spielt keine Rolle,
da wir uns dieses Stück dann am Rückweg ersparen können.
(18)+(12+s)+(12-s)

[kad]

Ein Rätsel für alle.

Bestimme den Umfang

287DA547-85B6-48C9-AFC7-4360D757D291.jpeg

Spoiler

Der Umfang ist 42.
2*(9+12)
Dass wir zischendurch schon mal ein Stück (s) zurücklaufen, spielt keine Rolle,
da wir uns dieses Stück dann am Rückweg ersparen können.
(18)+(12+s)+(12-s)

Spoiler

Das ist richtig

[kad]

Eine sehr grosse Torte wird auf 100 Gäste aufgeteilt.
Der erste Gast bekommt 1% der Torte. Der zweite Gast bekommt 2% der übrig gebliebenen Torte. Der dritte Gast bekommt 3% der übrig gebliebenen Torte…..
Der 100. Gast bekommt 100% der übrig gebliebenen Torte (also den ganzen Rest).

Welcher Gast bekommt das grösste Stück Torte?

[giffi marauder]

Eine sehr grosse Torte wird auf 100 Gäste aufgeteilt.
Der erste Gast bekommt 1% der Torte. Der zweite Gast bekommt 2% der übrig gebliebenen Torte. Der dritte Gast bekommt 3% der übrig gebliebenen Torte…..
Der 100. Gast bekommt 100% der übrig gebliebenen Torte (also den ganzen Rest).

Welcher Gast bekommt das grösste Stück Torte?

Spoiler

Der i-te Gast bekommt also (Produkt(j=1..i-1) (1-j/100))*i/100
Das ist dann der 10. mit 10% von noch 62,82% also 6,282% der gesamten Torte.

[kad]

Eine sehr grosse Torte wird auf 100 Gäste aufgeteilt.
Der erste Gast bekommt 1% der Torte. Der zweite Gast bekommt 2% der übrig gebliebenen Torte. Der dritte Gast bekommt 3% der übrig gebliebenen Torte…..
Der 100. Gast bekommt 100% der übrig gebliebenen Torte (also den ganzen Rest).

Welcher Gast bekommt das grösste Stück Torte?

Spoiler

Der i-te Gast bekommt also (Produkt(j=1..i-1) (1-j/100))*i/100
Das ist dann der 10. mit 10% von noch 62,82% also 6,282% der Torte.

Spoiler

Richtig. Zu leicht für dich!

Es hat aber noch ein paar Rätsel offen, die knackig sind.

[giffi marauder]

Eine sehr grosse Torte wird auf 100 Gäste aufgeteilt.
Der erste Gast bekommt 1% der Torte. Der zweite Gast bekommt 2% der übrig gebliebenen Torte. Der dritte Gast bekommt 3% der übrig gebliebenen Torte…..
Der 100. Gast bekommt 100% der übrig gebliebenen Torte (also den ganzen Rest).

Welcher Gast bekommt das grösste Stück Torte?

Spoiler

Der i-te Gast bekommt also (Produkt(j=1..i-1) (1-j/100))*i/100
Das ist dann der 10. mit 10% von noch 62,82% also 6,282% der Torte.

Spoiler

Richtig. Zu leicht für dich!

Es hat aber noch ein paar Rätsel offen, die knackig sind.

Spoiler

Na ja, beim Versuch obiges in eine Formel zu gießen und daraus einen Extremwert zu berechnen,
bin ich kläglich gescheitert.

[kad]

Eine sehr grosse Torte wird auf 100 Gäste aufgeteilt.
Der erste Gast bekommt 1% der Torte. Der zweite Gast bekommt 2% der übrig gebliebenen Torte. Der dritte Gast bekommt 3% der übrig gebliebenen Torte…..
Der 100. Gast bekommt 100% der übrig gebliebenen Torte (also den ganzen Rest).

Welcher Gast bekommt das grösste Stück Torte?

Spoiler

Der i-te Gast bekommt also (Produkt(j=1..i-1) (1-j/100))*i/100
Das ist dann der 10. mit 10% von noch 62,82% also 6,282% der Torte.

Spoiler

Richtig. Zu leicht für dich!

Es hat aber noch ein paar Rätsel offen, die knackig sind.

Spoiler

Na ja, beim Versuch obiges in eine Formel zu gießen und daraus einen Extremwert zu berechnen,
bin ich kläglich gescheitert.

Spoiler

Sei Gi, was der ite Gast bekommt.

Wenn du G(i+1)/Gi. ausrechnest, bekommst du einen Ausdruck. Dieser Ausdruck sollte > 1 sein (dann nimmt der Kuchenanteil zu).
Das führt zu 100> i^2+i. Daraus kann man leicht folgern, dass G10 das grösste Stück hat.

[kad]

Ein Frosch sitzt am Rande eines langen Teiches. Vor ihm sind 100 Seerosenblätter in einer Reihe bis ans gegenüberliegende Ufer angeordnet. Der Frosch hüpft entweder aufs nächste Seerosenblatt oder, mit Anstrengung, aufs übernächste Blatt. Immer Vorwärts. Auf wieviele verschiedene Arten hüpft er bis zu Seerosenblatt 100? (Immer aufs nächste Blatt zu hüpfen und somit alle 100 Seerosenblätter zu „besuchen“ ist eine Möglichkeit).

[giffi marauder]

Ein Frosch sitzt am Rande eines langen Teiches. Vor ihm sind 100 Seerosenblätter in einer Reihe bis ans gegenüberliegende Ufer angeordnet. Der Frosch hüpft entweder aufs nächste Seerosenblatt oder, mit Anstrengung, aufs übernächste Blatt. Immer Vorwärts. Auf wieviele verschiedene Arten hüpft er bis zu Seerosenblatt 100? (Immer aufs nächste Blatt zu hüpfen und somit alle 100 Seerosenblätter zu „besuchen“ ist eine Möglichkeit).

Spoiler

macht er 100 1'er Hüpfer gibts genau 100 über 0, also 1 Möglichkeit
macht er 98 1'er und 1 2'er gibts 99 Möglichkeiten also 99 über 1
macht er 96 1'er und 2 2'er gibts 98 über 2 Möglichkeiten
...
macht er 2 1'er und 49 2'er gibts noch 49 (49 über 1)
und schließlich nur noch 1 Möglichkeit für 50 2'er (50 über 0)
Damit haben wir gesamt die Summe von i=0..50 (n-i) über i, also von 51 Binomialkoeffizenten.
Natürlich sind das nicht jene von 2^50, sondern der erste (ganz links) der erste von n^100,
der 2. der 2. von n^99 ... bis ganz rechts als 51. den 51. von 2^50
Also beginnend mit 2^100 von links nach rechts immer eine Zeile hoch im Pascalschen Dreieck.

Diese Zahl ist jedenfalls > 2^50, d.h. mit rechnen kommen wir da nicht weiter.

Schauen wir uns das mal für kleine n an (wobei uns die ungeraden eigentlich nicht wirklich interessieren),
vielleich erkennen wir da ein Schema.
Anzahl der Blätter: Möglichkeiten
n:m
1:1
2: 2 (1+1)
3: 3
4: 5 (1+3+1)
5: 8
6: 13 (1+5+6+1)
7: 21
8: 34 (1 +7+15+10+1)
9: 55
10: 89 (1+9+28+35+15+1)
11: 34
12: 233


damit ist m=f(100) wohl die 100. Fibonacci-Zahl, also irgendwas bei 3,54225*10^20

[kad]

Ein Frosch sitzt am Rande eines langen Teiches. Vor ihm sind 100 Seerosenblätter in einer Reihe bis ans gegenüberliegende Ufer angeordnet. Der Frosch hüpft entweder aufs nächste Seerosenblatt oder, mit Anstrengung, aufs übernächste Blatt. Immer Vorwärts. Auf wieviele verschiedene Arten hüpft er bis zu Seerosenblatt 100? (Immer aufs nächste Blatt zu hüpfen und somit alle 100 Seerosenblätter zu „besuchen“ ist eine Möglichkeit).

Spoiler

macht er 100 1'er Hüpfer gibts genau 100 über 0, also 1 Möglichkeit
macht er 98 1'er und 1 2'er gibts 99 Möglichkeiten also 99 über 1
macht er 96 1'er und 2 2'er gibts 98 über 2 Möglichkeiten
...
macht er 2 1'er und 49 2'er gibts noch 49 (49 über 2)
und schließlich nur noch 1 Möglichkeit für 50 2'er (50 über 0)
Damit haben wir gesamt die Summe von i=0..50 (n-i) über i, also von 51 Binomialkoeffizenten.
Natürlich sind das nicht jene von 2^50, sondern der erste (ganz links) der erste von n^100,
der 2. der 2. von n^99 ... bis ganz rechts als 51. den 51. von 2^50
Also beginnend mit 2^100 von links nach rechts immer eine Zeile hoch im Pascalschen Dreieck.

Diese Zahl ist jedenfalls > 2^50, d.h. mit rechnen kommen wir da nicht weiter.

Schauen wir uns das mal für kleine n an (wobei uns die ungeraden eigentlich nicht wirklich interessieren),
vielleich erkennen wir da ein Schema.
Anzahl der Blätter: Möglichkeiten
n:m
1:1
2: 2 (1+1)
3: 3
4: 5 (1+3+1)
5: 8
6: 13 (1+5+6+1)
7: 21
8: 34 (1 +7+15+10+1)
9: 55
10: 89 (1+9+28+35+15+1)
11: 34
12: 233


damit ist m=f(100) wohl die 100. Fibonacci-Zahl, also irgendwas bei 3,54225*10^20

Ah, shit, oben stimmt was nicht.
macht er 1 2'er hat er keine 99 Möglichkeiten für diesen, sondern nur 98
Also nochmal von vorn.

Spoiler

Das mit der 100. Fibonacci Zahl stimmt natürlich.