Wie löst man diese Matheaufgabe(Wahrscheinlichkeiten)?

Davina denkt sich eine natürliche Zahl von 1 bis 10. Paco soll diese Zahl erraten.Er darf Fragen stellen, die Davina nur mit ,,ja´´ oder ,,nein´´ beantwortet. Zwei Strategien stehen zur Wahl :

Strategie 1: Die Zahlen werden der Reihe nach abgefragt.

Strategie 2: Mit jeder Frage wird versucht, möglichst die Hälfte der verbleibenden Zahlen auszusondern.

Welche der beiden Strategien soll Paco wählen ?

Ich denke, dass er mit Strategie 2 weniger auf Glück angewiesen ist.

Answer 1

[mihisu]

Da kann man unterschiedliche Begründungen geben.

====== Worst Case ======

Man könnte sich ansehen, wie viele Schritte man im schlechtesten Fall stellen muss.

Bei Strategie 1 kann es sein, dass man bei den ersten 8 Fragen falsch liegt. Dann klärt die 9te Frage, welche Zahl es ist. Man braucht im schlechtesten Fall also 9 Fragen.

Bei Strategie 2 hat man, wenn es schlecht läuft... nach der ersten Frage noch 5 in Frage kommende Zahlen (da 10/2 = 5); nach Frage 2 noch 3 in Frage kommende Zahlen (da 5/2 = 2,5 aufgerundet 3); nach Frage 3 noch 2 in Frage kommende Zahlen (da 3/2 = 1,5 aufgerundet 2); und die 4te Frage klärt dann, welche Zahl es ist. Man braucht im schlechtesten Fall also 4 Fragen.

Demnach könnte man sagen, dass Startegie 2 in dieser Hinsicht besser ist, da man im schlimmsten Fall weniger Fragen braucht.

====== Best Case ======

Man könnte sich ansehen, wie viele Schritte man im besten Fall stellen muss.

Bei Strategie 1 kann es sein, dass man bei der ersten Fragen richtig liegt.

Bei Strategie 2 hat man, wenn es gut läuft... nach der ersten Frage noch 5 in Frage kommende Zahlen (da 10/2 = 5); nach Frage 2 noch 2 in Frage kommende Zahlen (da 5/2 = 2,5 abgerundet 2); und die 3te Frage klärt dann, welche Zahl es ist. Man braucht im besten Fall 3 Fragen.

Demnach könnte man sagen, dass Startegie 1 in dieser Hinsicht besser ist, da man im besten Fall weniger Fragen braucht.

====== Erwartungswert ======

Man könnte sich ansehen, wie groß der Erwartungswert für die Anzahl der zu stellenden Fragen ist. [Annahme: Jede der 10 Zahlen wird mit der gleichen Wahrscheinlichkeit von Davina gewählt.]

Bei Strategie 1 hat man für die Anzahl X an Fragen, die man stellen muss, um die Zahl zu finden, die folgende Wahrscheinlichkeitsverteilung...

$P(X=1)=\frac{1}{10}$

$P(X=2)=\frac{9}{10}\cdot \frac{1}{9}=\frac{1}{10}$

$P(X=3)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{1}{8}=\frac{1}{10}$

$P(X=4)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{1}{7}=\frac{1}{10}$

$P(X=5)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{6}{7}\cdot\frac{1}{6}=\frac{1}{10}$

$P(X=6)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{6}{7}\cdot\frac{5}{6}\cdot\frac{1}{5}=\frac{1}{10}$

$P(X=7)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{6}{7}\cdot\frac{5}{6}\cdot\frac{4}{5}\cdot\frac{1}{4}=\frac{1}{10}$

$P(X=8)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{6}{7}\cdot\frac{5}{6}\cdot\frac{4}{5}\cdot\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{10}$

$P(X=9)=\frac{9}{10}\cdot \frac{8}{9}\cdot \frac{7}{8}\cdot\frac{6}{7}\cdot\frac{5}{6}\cdot\frac{4}{5}\cdot\frac{3}{4}\cdot\frac{2}{3}=\frac{2}{10}$

Für den Erwartungswert der Anzahl an Fragen erhält man dann bei Strategie 1:

$E(X)=\frac{1}{10}\cdot 1+\frac{1}{10}\cdot 2+\frac{1}{10}\cdot 3+\frac{1}{10}\cdot 4+\frac{1}{10}\cdot 5+\frac{1}{10}\cdot 6+\frac{1}{10}\cdot 7+\frac{1}{10}\cdot 8+\frac{2}{10}\cdot 9=5\text{,}4$

D.h. man braucht durchschnittlich 5,4 Fragen bei Strategie 1.

------------

Bei Strategie 2 hat man nach der ersten Frage auf jeden Fall noch 5 in kommende Zahlen. Mit der nächsten Frage teilt man diese 5 Zahlen in einer 3er- und eine 2er-Gruppe ein.

Mit einer Wahrscheinlichkeit von 2/5 ist die Zahl nach der zweiten Frage in der 2er-Gruppe, sodass man die Zahl dann im nächsten Schritt mit der dritten Frage findet.

Mit einer Wahrscheinlichkeit von 3/5 ist die Zahl nach der zweiten Frage in der 3er-Gruppe. Diese 3 Zahlen werden dann mit der dritten Frage in eine 1er- und eine 2er-Gruppe eingeteilt. Bei dieser dritten Frage hat man mit einer bedingten Wahrscheinlichkeit von 1/3 die Zahl gefunden; und mit einer bedingten Wahrscheinlichkeit von 2/3 hat man noch 2 in Frage kommende Zahlen, sodass dann die Zahl mit der 4ten-Frage findet.

Dementsprechend lautet hier die Wahrscheinlichkeitsverteilung für die Anzahl der Fragen...

$P(X=3)=\frac{2}{5}+\frac{3}{5}\cdot\frac{1}{3}=\frac{3}{5}$

$P(X=4)=\frac{3}{5}\cdot\frac{2}{3}=\frac{2}{5}$

Für den Erwartungswert der Anzahl an Fragen erhält man dann bei Strategie 2:

$E(X)=\frac{3}{5}\cdot 3+\frac{2}{5}\cdot 4=3\text{,}4$

D.h. man braucht durchschnittlich 3,4 Fragen bei Strategie 2.

------------

Demnach könnte man Strategie 2 bevorzugen, da man da durchschnittlich weniger Fragen braucht.

====== Streuung/Standardabweichung ======

Die Standardabweichung für die Anzahl der Fragen beträgt bei Startegie 1 ungefähr 2,73 und bei Strategie 2 ungefähr 0,49.

Demnach könnte man Strategie 2 bevorzugen, wenn man möchte, dass das Spiel immer ungefähr gleich lang dauert, statt dass die Anzahl der Fragen (und dementsprechend die Spiellänge) stark schwankt.

Comments

[eterneladam]

Absolut richtig, Bewertungskriterien für die Strategien festzulegen. Bei Worst Case sind es bei Strategie 1 neun Fragen.der zugehörige Erwartungswert 4.5.

Answer 2

[TUrabbIT]

Strategie 2 ist effizienter, nennt sich übrigens binäre Suche.

Solange aber die Zahl der Fragen unbegrenzt ist, kommt man mit beiden Zahlen zum Ziel und bei 10 Zahlen auch relativ schnell.

Bei größeren Zahlenmengen oder wenn die Zahl der Fragen relevant ist, ist Strategie 2 zunehmend sinnvoller.