König und sein Gefängnis

Freizeit & Hobby Rätsel
#1

Ein König hat ein Gefängnis mit 100 Zellen.
Eines Tages sind alle Zellen mit Gefangenen belegt.
Da er kein Geld hat um mehr Zellen zu bauen muss er einige Gefangene freilassen um wieder Platz für neue Verbrecher zu haben.
Deswegen geht er in der nächsten Nacht ins Gefängnis und schliesst alle Türen auf.
Als er wieder im Bett liegt denkt er: „Ich darf nicht alle Verbrecher auf einmal freilassen“. Deswegen steht er auf und schliesst jede zweite Türe wieder zu.
Danach ist er immer noch nicht zufrieden. Desegen dreht er an jeder dritten Türe den Schlüssel um. (d.h. er schliesst die 3. Tür zu, öffnet die 6. Tür, schliesst die 9. Tür, usw.)
So fährt dann mit jeder vierten, fünften, … bis zur hundertsten Türe fort.
Am folgenden Morgen flüchten alle Gefangenen mit offener Türe.

Die Frage lautet: Wieviel Zellen sind jetzt leer?

Zusatzfrage: Wie lautet die Antwort wenn es eine Million Zellen gibt?

#2

Hallo,
ich vermute das er z.B. im Schritt, wo jede vierte Tür verschlossen werden soll, die vierte Tür (die ja bereits beim Verschliessen jeder zweiten Tür geschlossen wurde), wieder aufschließt - sozusagen den Geschlossen-/Unverschlossen Zustand immer umdreht ? Dann können ⌊sqrt(n)⌋ Gefangene flüchten.

Gruss
Enno

#3

Nachtrag (Spoiler)
Hallo,
man argumentiert über die Anzahl der Teiler der Zahlen im betrachteten Intervall. Ist die ungerade ist die Tür letztlich offen, ist sie gerade ist sie (letztlich) verschlossen. Die Behauptung ist nun:

T(m) ungerade gdw. m=k2 ist Quadratzahl (*)

wobei T(m) die Anzahl der Teiler von m ist. Damit wären alle Zellentüren offen, deren Nummer eine Quadratzahl ist und davon gibt es bei insgesamt n Zellen gerade die erwähnte Anzahl. Die Behauptung beweißt man leicht, wenn man die Primzahlfaktorisierung von m berücksichtigt.

Zur Aussage T(k2) ist ungerade.
Sei k=∏1 p(i)a(i). Dann ist T(k)=∏1 (a(i)+1), k2=∏1 p(i)2a(i) und T(k2)=∏1 (2a(i)+1) und damit ein Produkt aus durchweg ungerade Faktoren und somit ungerade.

Sei umgekehrt T(m) ungerade, für m=∏1 p(i)a(i) und T(m)=∏1 (a(i)+1) folgt damit das alle a(i) gerade sind, resp. a(i)+1 ungerade. Damit ist m=(∏1 p(i)a(i)/2)2, also eine Quadratzahl.

Gruss
Enno

1 Like
#4

Hallo Loitz,
Mein Excel-Makro hat gesagt, daß 49 Gefangene flüchten können.
Bin zu faul zum rechnen, aber trotzdem neugierig, ob´s stimmt.

Grüße, Fritz

#5

Hallo NaSowas,

Mein Excel-Makro hat gesagt, daß 49 Gefangene flüchten können.
Bin zu faul zum rechnen, aber trotzdem neugierig, ob´s stimmt.

Vielleicht hast du dir ja schon mal die Antwort von Enno angeschaut. Er liefert einen recht einfachen Beweis für die Behauptung, dass die Anzahl O der am Morgen offenstehenden Türen O=[sqrt(N)] beträgt, falls N die Gesamzanzahl der Türen ist (Die eckige Klammer soll die Gaußklammer sein, d.h. [x] bezeichnet die größte ganze Zahl, die nicht größer ist als x). Bei deinem Excel-Makro muss also irgenwas schiefgelaufen sein ([sqrt(100)]=10≠49).

Gruß
Jens

#6

Hallo,
evtl. eine Frage, wie die Aufgabenstellung interpretiert wurde. Die war mir ja auch nicht 100% klar. Ich vermute nur, daß sie so, wie ich sie jetzt angenommen habe richtig ist, weil das Ergebnis ästhetisch ist *g*.

Gruss
Enno

#7

Hallo jns4sen,

Mit der Aussage, daß

([sqrt(100)]=10≠49)

hast du sicherlich recht. 10 49.
Wenn ich aber von 100 offenen Türen 50 schließe, und dann an jeder 3. den Schließzustand umkehre (also an maximal 33,3 Türen), muß etwas mehr übrig bleiben als 10. Wenn es noch so läuft, daß ich nur offene Türen schließe, bleiben immer noch 16,6 offene Türen übrig (50 - 33,3), die ich nicht berührt habe…
Willst du das Makro (und die dazugehörige Mappe) mal sehen?

Grüße, Fritz

#8

zur Lösung
Glückwunsch zur Lösung.

Ich dachte die Aufgabe sei eindeutig gestellt, wenn ich den Schlüssel umdrehe wird eine offene Türe abgeschlossen und eine abgeschlossene Tür aufgeschlossen.
In der realen Welt gibt es natürlich auch Türen die man zweimal oder noch öfters abschliessen kann.

Hier noch eine Bemerkung zur Lösung.
Man kann auch ohne Primfaktorzerlegung zeigen, dass genau die Quadratzahlen eine ungerade Teileranzahl haben.

Fall n ist keine Quadratzahl:
Dann ist SQRT(n) keine ganze Zahl. Deswegen treten die Teiler von n immer paarweise auf, d.h. ist r ein Teiler von n, dann ist auch s:=n/r ein Teiler von n und r ist ungleich s (r,s sollen natürliche Zahlen sein).
=> # Teiler von n ist gerade.

Fall n eine Quadratzahl:
Dort treten die Teiler wie oben auch paarweise auf, aber zusätzlich gibt es noch
SQRT(n) als Teiler von n.
=> # Teiler von n ist ungerade.

#9

Hallo,
bin zwar nicht Jens aber das Makro würde mich schon interessieren. Evtl. klären sich dann die Differenzen.

Gruss
Enno

#10

Kriegst Du per Mail. OK?

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#11

Hallo,

Kriegst Du per Mail. OK?

ok.

Gruss
Enno

#12

Vertraue besser nicht auf ein Microsoft Programm …
erst recht nicht, wenn du den Code selbst geschrieben hast.

#13

Hallo,
die Lsg. ist mir gestern abend auf Umwegen (wieder über die Primzahlfaktorisierung) auch noch eingefallen. Finde ich deutlich eleganter, da sie kürzer ist und weniger vorraussetzt.

Gruss
Enno

#14

Unterschied
Hallo,
das Makro betrachtet (wenn ich mich nicht irre) nur die Fälle, daß jede zweite Tür wieder verschlossen wird und danach für alle Vielfachen von 3 (3,6,9,…) der Zustand umgedreht wird. Probier mal aus, was passiert, wenn Du das Spiel für alle Vielfachen von 4 (4,8,12,…), 5 etc. bis 100 fortsetzt.

Gruss
Enno

#15

Wer lesen kann :o)
ist einwandfrei im Vorteil.
Hab meinen Denkfehler entdeckt.

Gruß

#16

Vertraue besser nicht auf ein Microsoft Programm …
erst recht nicht, wenn du den Code selbst geschrieben hast.

Es ist nicht das Programm, es war meine Denkweise und dadurch der Code
;o)