Wpis z mikrobloga

#zagadkilogiczne

(Odpowiedzi umieszczajcie w spoilerze. W nowej linii: wykrzyknik, spacja, odpowiedź)

Załóżmy, że grasz ze znajomym w taką grę: znajomy wybiera liczbę od 1 do 9, a Ty odgadujesz jaką liczbę pomyślał, zadając pytania na które można odpowiedzieć TAK lub NIE. Mógłbyś postępować wg poniższego toku: czy liczba jest większa niż 4? Jeśli odpowiedź brzmi tak to zadajesz kolejne pytanie: czy jest większa niż 8? Jeśli tak, to odpowiedzią jest 9. Jeśli nie, to odpowiedzią jest 7 lub 8, więc będzie potrzebne jeszcze jedno pytanie. Jeśli odpowiedź na pierwsze pytanie brzmiała "nie", to pytasz: czy liczba jest większa niż 2? Jeśli tak, to liczbą jest 3 lub 4, więc potrzeba jeszcze jednego pytania; jeśli nie, to liczbą jest 1 lub 2 więc też potrzeba jeszcze jednego pytania.

Wniosek jest taki: jeśli znajomy pomyślał liczby: 1,2,3,4,5,6 lub 9 to potrzebujesz trzech pytań, a jeśli 7 lub 8 - potrzebujesz czterech pytań. Wartość oczekiwana liczby pytań wynosi 7/93+2/94=29/9=3,22. Średnio, potrzeba więc 3,22 pytania by odgadnąć liczbę.

W poprzednim problemie zakładaliśmy, że prawdopodobieństwo wyboru każdej liczby jest takie samo. Jakby jednak zmieniło się rozwiązanie, gdyby było inaczej?

Rozważmy taki problem: mamy talię kart składającą się z samych kart kierowych: jeden as, dwie dwójki, trzy trójki, cztery czwórki, …, dziewięć dziewiątek. W sumie 45 kart. Ta talia jest przetasowywana i znajomy wybiera jedną kartę. Znów zadajemy tylko pytania na które można odpowiedzieć TAK lub NIE. Jaka może być najlepsza (najmniejsza) wartość oczekiwana liczby pytań? Jakie pytania należy zadawać?
  • 13
@almafater: "czy liczba jest większa niż 4? Jeśli odpowiedź brzmi tak to zadajesz kolejne pytanie: czy jest większa niż 8? Jeśli nie, to odpowiedzią jest 7 lub 8" A czemu nie 5 lub 6? Uciąłeś coś?
@TOFAN: Ech, minął mi czas na edycję.

Więc jeszcze raz ten proces z przykładu:

Czy liczba jest większa niż 4? Jeśli tak, to pytasz: czy jest większa niż 6? Jeśli nie to liczba wynosi 5 lub 6 więc potrzeba jeszcze jednego pytania. Jeśli tak, to pytasz: czy jest większa niż 8? Jeśli tak, to wynosi 9. Jeśli nie, to wynosi 7 lub 8 więc potrzeba jeszcze jednego pytania. Jeśli odpowiedź na
@almafater:


TAK: czy równa 9?


TAK: 9 w 2 odpowiedziach


NIE: Czy równa 7?


TAK: 7 w 3


NIE: 8 w 3


NIE: czy większa niż 4?


TAK: Czy równa 5?


TAK: 5 w 3


NIE: 6 w 3


NIE: Czy równa 4?


TAK: 4 w 3


NIE: Czy równa 3?


TAK: 3 w 4


NIE: Czy równa 2?


TAK: 2 w 5


NIE: 1 w 5


Likwiduje wcięcia i nic