Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Makabere Kopfnuss, doch echt schwierig

ZahlReich - Mathematik Hausaufgabenhilfe » Denksport » Kopfnüsse 2 » Makabere Kopfnuss, doch echt schwierig « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin Muskala (Mellek)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 02. November, 2001 - 14:09:   Beitrag drucken

Nachfolgende Problemstellung soll als rekursive/explizite Folge allgemeingültig ausgedrückt werden. Ok, ich gebe zu, dass das Beispiel etwas makaber ist, aber so lautete die Aufgabe nun einmal:
41 Männer sind in einer Höhle eingeschlossen. Sie beschließen ihrem Leiden ein schnelles Ende zu bereiten, da sie nicht langsam dahinsiechen wollen. Dazu beschließen sie sich in einem Kreis aufzustellen, sich dann in Zweiergruppen zusammenzuschließen, um sich dann gegenseitig zu erstechen. Das soll wie folgt ablaufen. Der erste und der zweite bilden eine Zweiergruppe in der der erste dann abgemurkst werden soll. Der dritte und der vierte bilden ebenfalls eine Zweiergruppe in der der vierte den dritten kaltmacht. Das heißt also, das zum Schluss der ersten Runde alle Männer mit ungeraden Zahlen tot sind, außer der Nummer 41, denn der hatte keinen der ihn umbringen konnte. Die Überlebenden stehen weiterhin in diesem Kreis und fangen die ganze Prozedur von vorn an. Durch einen dummen Zufall ist man als einer der Männer mit in dieser Höhle gefangen, hat aber den Drang zu überleben. Einen Überlebenden wird es zum Schluss auf jeden Fall geben, doch an welcher Position muss dieser am Anfang stehen. Angeblich soll es zu diesem Problem eine Folge geben, die die Position an der man überlebt ausgibt, und zwar unabhängig von der Anzahl der Männer ,die sich in der Höhle befinden. Ich habe über dieser Geschichte schon einen gesamten Tag gebrütet und dabei nicht einmal im entferntesten einen Lösungsansatz gefunden. Ich hoffe dass ich die Aufgabenstellung hier nachvollziehbar darstellen konnte. Wäre toll, wenn jemand dies Problem mit anschaulichem Lösungsweg lösen könnte.

Vielen Dank
Martin
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Murray (Murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 02. November, 2001 - 14:53:   Beitrag drucken

Die Lösung ist erstmal:
- bei N Personen muß man an der Position ld(N) (abgerundeter Logarithmus zur Basis 2)

Bsp.: 41 Personen => Position 32
11 Personen => Position 8

Warum ist das so?
Da immer alle ungeraden gestrichen werden, muß man bis zur letzten Runde auf einer geraden Position stehen und das geht nur in einer Zweierpotenzreihe.

Ich habe mal unten Dein Beispiel aufgeführt und mit jedem Streichen nummeriere ich die Zahlen neu durch.

1 x
2 1 x
3 x
4 2 1 x
5 x
6 3 x
7 x
8 4 2 1 x
9 x
10 5 x
11 x
12 6 3 x
13 x
14 7 x
15 x
16 8 4 2 1 x
17 x
18 9 x
19 x
20 10 5 x
21 x
22 11 x
23 x
24 12 6 3 x
25 x
26 13 x
27 x
28 14 7 x
29 x
30 15 x
31 x
32 16 8 4 2 1
33 x
34 17 x
35 x
36 18 9 x
37 x
38 19 x
39 x
40 20 10 5 x
41 x

Murray
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 02. November, 2001 - 21:25:   Beitrag drucken

Ich glaube, ganz habe ich die Aufgabe noch nicht verstanden.

Wenn nach 20 "Spielzügen" die Männer 1, 3, ..., 39 den Löffel abgegeben haben, geht es dann in der nächsten Runde damit weiter, dass Nr. 2 die Nr. 41 absticht, oder wird Nr. 2 von Nr. 4 erledigt??

Bei N = 11 Männern bleibt im ersten Fall Nr. 11 und im zweiten Fall Nr. 6 schließlich übrig. Und nicht Nr. 8, wie Murray behauptet.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Fireangel (Fireangel)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 03. November, 2001 - 08:25:   Beitrag drucken

@Murray:
du hast nicht bedacht, dass Nr.41 am Anfang nicht umkommt, er hat ja keinen Mörder mehr mit der Nr.42.

Das ist auch schon die logische Lösung. Wenn jeder in dieser Spiel von demjenigen mit der nächsthöheren Nummer umgebracht wird, und die Numerierung sich nicht willkürlich ändert, dann muss der mit der höchsten Startnummer in jedem Fall überleben.
Wenn sich die Nummerierung ändert, z.B. so, dass der letzte in der Reihe, der jeweils keinen Mörder mehr hatte, nun die Nummer 1 kriegt, dann muss immer der mit der Nummer zwei überleben, da er diese Nummer die ganze Prozedur über behält.
Wird nach anderen Regeln nummeriert, müssten die zu einer Beschreibung der Überlebensstrategie erst dargestellt werden, da es zu viele Möglichkeiten gibt, um hier durchzuraten.

Fireangel
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 03. November, 2001 - 13:57:   Beitrag drucken

Hi,

es ist wohl anscheinend so, dass nachdem 40 die 39 gekillt hat, 41 von 2 ins Jenseits befördert wird.

Denn würde es wieder von vorne losgehen, also 4 ersticht 2, dann bleibt ja in der Tat (wie von Murray richtigt beobachtet) der Mann mit der höchsten Nummer, also die 41, übrig.

Außerdem wäre dann die Information, dass die Männer im Kreis stehen überflüssig. Sie könnten sich auch in einer Linie aufstellen.

Es sei f(N) aus {1, 2, ..., N} der Überlebende. Dann gilt

f(1) = 1
f(N+1) = 2 + (f(N) mod N)

Wir rechnen einige Werte aus:

N = 1: 1
N = 2: 2
N = 3: 2
N = 4: 4
N = 5: 2
N = 6: 4
N = 7: 6
N = 8: 8
N = 9: 2
N = 10: 4
N = 11: 6
...
N = 16: 16
N = 17: 2
N = 18: 4
N = 19: 6
...
N = 32: 32
N = 33: 2
N = 34: 4
N = 35: 6
...
N = 41: 18
...
N = 64: 64
N = 65: 2
N = 66: 4
N = 67: 6
...

Diese Beobachtung lässt folgenden Sachverhalt vermuten.

Wenn N eine Zweierpotenz, dann ist f(N) = N.

Ansonsten sei k maximal mit 2k < N. Dann ist f(N) = 2(N - 2k).
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Z
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 03. November, 2001 - 14:00:   Beitrag drucken

Sorry, die zitierte Beobachtung stammte nicht von Murray, sondern von Fireangel.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Murray (Murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 06. November, 2001 - 13:42:   Beitrag drucken

Hallo,

also erstmal revidiere ich meinen ersten Artikel.

Bisher waren ja nur Vermutungen gemacht wurde, das es der letzte Platz sein muß, welcher überlebt. Ich kann es nach einiger Überlegung nun definitiv bestätigen.

Der Einfachheit halber gehen wir mal davon aus, es stehen N Personen in einer Linie.

Wir betrachten zwei Fälle:

1.) N ist ungerade
- dann werden N/2 gestrichen (alle ungeraden) und der letzte, der keinen Killer hat bleibt übrig
2.) N ist gerade
- dann muß der letzte auch übrig bleiben
(da der letzte gerade ist und alle ungeraden gestrichen werden)

Die Züge enden immer damit das noch zwei Personen leben und der 2. den 1. killt.
Die Frage, wer überlebt, reduziert sich auf die letzte Runde. Wer nämlich dort an der letzten Position steht hat gewonnen und das passiert nur dem, der in der Runde davor am Ende steht (und so weiter).
Es ist auch egal ob die Anzahl gerade oder ungerade ist, das führt immer zum gleichen Ergebnis.

Bsp.:

1 x
2 1 x
3 2 1

1 x
2 1 x
3 x
4 2 1

Murray
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 06. November, 2001 - 18:59:   Beitrag drucken

Murray, mir scheint aber, dass die Aufgabe nicht so gemeint war (siehe mein Beitrag vom 3. Nov.).

Schade, dass der Fragesteller, der uns Aufschluss geben könnte, offenbar nicht mehr interessiert ist.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Fireangel (Fireangel)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 07. November, 2001 - 10:50:   Beitrag drucken

Das Prinzip dieses "Spieles" lässt sich meiner Meinung nach in zwei Stufen gliedern.

1. Jeder im Kreis erhält eine Nummer von 1 fortlaufend bis n, wobei n die Anzahl der jeweils noch lebenden Personen ist.

2. Jeder mit einer ungeraden Nummer wird anschliessend von demjenigen mit der darauffolgenden geraden Nummer umgebracht.

Die Antwort auf Frage wer am Ende überlebt, ergibt sich also aus der Art, wie die Nummern nach jedem Durchgang neu vergeben werden.
Am Anfang gibt es hier 41 Nummern für 41 Menschen.
Wenn nun nach dem ersten Morden die 1 neu vergeben werden muss, dann scheinen mir nur folgende Möglichkeiten logisch zu sein:

1.) Der, der vorher die 2 hatte, kriegt jetzt die 1, das würde heissen, dass der 41. des ersten Durchgangs jetzt die 21 erhielte und somit wieder überlebt etc. Er würde auch am Ende überbleiben.

2.) Der, der vorher die höchste Zahl hatte, kriegt nun die 1, das hiesse, das der, der am Anfang die zwei hatte, diese wieder erhält und das in jeder Runde, so dass er am Ende überlebt.

3.) Der, der die höchste Nummer hatte, kriegt die 1, wenn seine Nummer ungerade war, ansonsten kriegt der die 1, der vorher die 2 hatte. Das hiesse tabellarisch für unser Beispiel (jede Spalte stellt einen neuen Durchgang dar, der Einfachheit halber ab Runde zwei):

2,2,2,2,1
4,3
6,4,3
8,5
10,6,4,3
12,7
14,8,5
16,9
18,10,6,4,2,2,Überlebender
20,11
22,12,7
24,13
26,14,8,5
28,15
30,16,9
32,17
34,18,10,6,3,1
36,19
38,20,11,1
40,21,1
41,1

Dies führt zu der Formel, die Zaph bereits am 3.11. angegeben hat.

Welcher dieser drei Wege aber der richtige ist kann uns nur Martin Muskala(Mellek) sagen, indem er die Definition seiner Regeln erweitert.

Ein sicheres Überleben gestaltet sich allerdings einfacher, wenn man, da die anderen ja ihrem Leiden ein Ende bereiten wollen,sich erböte, sie sämtlichst umzubringen.

Fireangel
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 09. November, 2001 - 17:18:   Beitrag drucken

Variante 3 scheint mir die einzig vernünftige.

Eine etwas weniger blutrünstige Version ist die folgende.

Im Kreis stehen 41 Kinder, die einen Abzählreim aufsagen: "Ene mene muh und raus bist du!"

Bei welchem Kind der Reim endet, muss den Kreis verlassen. Beim nächsten Kind geht der Reim erneut los. Wer bis zum Schluss stehenbleibt, hat gewonnen.

Um mit obigem Beispiel analog zu sein, ist der Reim nur sehr kurz und reimt sich auch nicht: "Raus du!" Außerdem wird mit Kind 41 das Abzählen begonnen. Als erstes verlässt also Kind 1, dann Kind 3, 5, usw den Kreis. Nach Kind 39 ist Kind 41 dran und es geht mit Kind 4 weiter.

Wie lautet die Formel, wenn der Reim länger ist (k Silben)???

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page