"Zahlenspiel" < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:33 Mi 02.11.2005 | | Autor: | BoomBoom |
Ich habe diese Frage in keinem anderen Forum gestellt:
hallo zusammen 
ich hoffe ihr könnt mir bei meiner Frage behilflich sein...
Aufgabe:
Ein Spiel besteht daraus, dass sich eine Person (Quizmaster) eine Zahl z zwischen 0 und 99.999 ausdenkt (0 und 99.999 inklusive). Eine zweite Person (der Spieler) muss versuchen diese Zahl herauszubekommen. Er rät also im ersten Durchgang eine Zahl. Der Quizmaster verrät ihm nur ob die gesuchte Zahl getroffen wurde oder ob die gesuchte Zahl größer oder kleiner als die genannte Zahl ist. Wie oft muss der Spieler mindestens raten um eine beliebige Zahl zu erraten?
Wir gehen davon aus, dass der Spieler folgendermaßen vorgeht:
Da er immer gesagt bekommt, ob die gesuchte Zahl größer oder kleiner als die von ihm Genannte ist, wählt er immer die Zahl aus, die möglichst in der Mitte zwischen der Oberen und Unteren Grenze aller noch möglichen Zahlen steht.
Lösung 1
Die Anzahl der Zahlen die für die Zahl vorkommen halbiert sich immer:
[mm] \Rightarrow 2^{i}=100.000 \Rightarrow [/mm] i=16.61...
[mm] \Rightarrow [/mm] für i=17 Treffen wir mit Sicherheit alle Zahlen.
[mm] \Rightarrow [/mm] man benötigt 17 Versuche
Lösung 2
Diese ist leider etwas Länger. Aber genau darum dreht sich dann meine Frage...
[mm] M_{i} [/mm] sei die Menge aller noch zur Auswahl stehenden Zahlen im i-ten Schritt, von denen eine die "richtige" Zahl ist. z liegt immer in [mm] M_{i}
[/mm]
[mm] x_{i} [/mm] sei die Anzahl der Zahlen in [mm] M_{i} [/mm] also [mm] x_{i}=|M_{i}|
[/mm]
Z.b. ist [mm] x_{1}=1.00.000, [/mm] und [mm] M_{1}={0,1,2,...,99.999}
[/mm]
Der Spielerwählt dann 50.000
Um herauszufinden, wie viele Schritte der Spieler mindestens für jede Zahl benötigt müssen wir wissen für welches i die Menge [mm] M_{i} [/mm] nur noch ein Element enthält. Dieses Element ist dann die gesuchte Zahl.
Von Versuch zu Versuch Reduziert sich die Anzahl an Elementen in der Menge M (bzw.: [mm] x_{i} [/mm] wird von mal zu mal kleiner:
Fall 1: [mm] x_{i} [/mm] ist gerade [mm] \Rightarrow x_{i+1}=\bruch{x_{i} }{2}
[/mm]
Erklärung mit Hilfe von einem Beispiel
[mm] x_{i} [/mm] =10 ,
also besteht [mm] x_{i} [/mm] z.b. aus folgenden Zahlen:{0,1,2,3,4,5,6,7,8,9}
Hier gibt es keine eindeutige Mitte. Es bleibt immer eine Menge mit 4 und eine Menge mit 5 Elemente übring.
Wähle ich z.B. die 5 als Mitte, so erhalte ich für [mm] x_{i+1} [/mm] die verbleibenden Elemente {0,1,2,3,4} oder {6,7,8,9}.
Da ich wissen möchte wie viele Schritte man mindestens braucht, tue ich so als sei meine Zahl stets in der Menge die größer ist.
[mm] \Rightarrow x_{i+1}=\bruch{x_{i}}{2}
[/mm]
Fall 2: [mm] x_{i} [/mm] ist ungerade [mm] \Rightarrow x_{i+1}=\bruch{x_{i}-1 }{2}
[/mm]
[mm] \Rightarrow [/mm] die Menge teilt sich im nächsten Schritt in Zwei mengen mit der "Größe" [mm] \bruch{x_{i}-1 }{2} [/mm] auf, da eine Menge von Ungeraden Zahlen immer ein eindeutige "Mitte" hat
wieder ein Beispiel
sei [mm] M_{i}={2,3,4,5,6} \Rightarrow x_{i} [/mm] =5
der Spieler wählt nun immer die Mitte, also die 4:
[mm] \Rightarrow M_{i+1}={2,3} [/mm] oder [mm] M_{i+1}={5,6} \Rightarrow x_{i+1}=\bruch{x_{i}-1 }{2}
[/mm]
Nun folgte ein Tabelle aus der die Lösung ersichtlich ist
Versuch Nr.: [mm] x_{i}
[/mm]
1 100.000
2 50.000
3 25.000
4 12500
5 6250
6 3125 (zum ersten mal Fall 2)
7 (3125-1)/2=1562
8 781
9 390
10 195
11 97
12 48
13 24
14 12
15 6
16 3
17 1
[mm] \Rightarrow [/mm] Beim 17 ten Zug hat man die Zahl mit Sicherheit gefunden
Sind beide Lösungen richtig? Ist Lösung 2 zu kompliziert gedacht?
Da fällt mir gerade ein, könnte ich Lösung 1 vielleicht auch so erklären:
mit dem letzten versuch decke ich 2 zahlen ab, mit dem vorletzten 2*2, mit dem davor 2*2*2 usw. Wie viele Schritte muss ich also machen, damit mitdestens 100.000 Zahlen abgedeckt sind? dies sind gerade 17 weil [mm] 2^{16}<100.000 [/mm] und [mm] 2^{17 }>100.000?
[/mm]
danke dass ihr bis hier her gelesen habt... Wenn ich etwas zu ungenau oder unverständlich geschrieben habe dann sagt es ruhig..  dann versuche ich nämlich es das nächste mal besser zu machen
Ich wünsche euch noch einen schönen Tag
gruß
BoomBoom
|
|
| |
|
Hallo BoomBoom,
Du musst Dich unbedingt an Lösung 2 halten, da Du dort die Gewinnstrategie mit angibst.
In Lösung 1 behauptest Du, dass sich die Anzahl der verbliebenen Zahlen in jedem Schritt halbiert. Das ist im Wesentlichen richtig, und in Lösung 2 gibst Du ganz genau an, wie Du die Halbierung durchführst.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:12 Sa 05.11.2005 | | Autor: | BoomBoom |
Hallo holy_diver_80
ok.. als dann noch einen Schönen Tag und danke für deine Antwort
schöne Grüße
BoomBoom
|
|
|
|
