1000 Leute stellen sich in einem Kreis auf, von der Nummer Eins bis zur Tausend.
Eine weitere Person schreitet nun, beginnend bei Nummer Eins, den Kreis ab und wirft jeden zweiten raus, bis nur noch einer übrig ist.
An welche Position muß man sich am Anfang stellen, um am Ende übrig zu bleiben?
Kommt jemand drauf?
zum verständnis bei einem Kreis von 10 sieht das ganze dann so aus.
(1 2 3 4 5 6 7 8 9 10)
(1 3 5 7 9) --> nach dem 1. Durchgang
(1 5 9) --> nach dem 2. Durchgang
( 5 ) --> zum Schluss
Hallo,
nur ein Tip (da bisher unverifiziert). Schau Dir mal die Binärdarstellung von 10 und 5, sowie einigen anderen Bsp. an. Wenn meine These stimmt, kommt bei 1000, 125 raus. Müßte ich mir morgen aber noch mal genauer anschauen.
Hallo TwingO,
der Tipp von Enno mit der Binärdarstellung ist wirklich sehr hilfreich. Stellt man die Anzahl N der Personen binär dar (N=a_0*2^0+a_1*2^1+…+a_i*2^i+…+a_n*2^n, a_i aus {0,1}, a_n=1), so ergibt sich die gesuchte Zahl M folgendermaßen durch Rotation der Bitfolge: M=a_n*2^0+a_0*2^1+a_1*2^2+…+a_i*2^(i+1)+…+a_(n-1)*2^n.
Für N=1000 erhält man auf diese Weise M=977, d.h. die Person mit der Nummer 977 bleibt als letzte übrig.
Natürlich lässt sich meine Behauptung auch beweisen. Dazu braucht man sich nur vor Augen zu führen, dass sich die Differenz der Anfangsnummern der noch übriggeblibenen Personen nach jeder Runde verdoppelt, also nach der i-ten Runde 2^i beträgt. Jetzt braucht man sich nur noch zu überlegen, unter welchen Umständen sich die kleinste noch übrig gebliebene Anfangsnummer ändert und wann nicht (wenn sie sich ändert, dann erhöht sie sich um 2^i). Ein formaler Beweis kann evtl. am Mathe-Brett ersucht werden.
Viele Grüße
Jens
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo Enno,
eine sehr gute Idee, das mit der Binärdarstellung. Aber 125 ist falsch. Hast du dich bei der Umrechnung von Dezimal- in Binärdarstellung (oder umgekehrt) verrechnet?
Viele Grüße
Jens
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
nein ich habe falsch geraten. Ich dachte man teilt durch 2, bis die Zahl ungerade wird. Die Bsp. die ich in der Kürze durchexerziert habe, waren alle so geartet, daß das selbe wie bei Deiner zyklischen Rotation rauskam - also nicht aussagekräftig genug.
Hinzuzufügen …
… wäre max. das diese Listennotation (wie bei Dir) irreführend ist. Es ist nicht ersichtlich, welche Zahl im nächsten Durchgang als erste Position gewertet wird. Das Bsp. für 1-10 würde man m.M. besser so notieren:
Auf 977 bin ich auch gekommen, aber unten aufgeführte Liste verstehe ich nicht (gib zu:smile:))). In einem Kreis gibt es keine „erste“ oder „letzte“ Position. Dritte Zeile: müsste daher mit 5 anfangen…ODER?
Viele Grüße
Kathleen
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
die Listen, die ich hier aufführe spulen den Kreis ab der ersten Position (für die nächste Runde) ab. Vorteil - man kann ausschließlich anhand der Liste (und nicht der gesamten Historie) die Nachfolgeliste bestimmen. Schreibe ich z.B. [1,5,9] statt [9,1,5] ist nicht ersichtlich, daß das erste Element der neuen Zählung die 9 und nicht die 1 ist.