. Nmn: Załóżmy że mamy coś takiego Wybieramy liczbę od 0 do 150, z 0 włącznie. Za każdym razem, dostajemy wiadomość czy szukana liczba jest większa czy mniejsza. Mamy 5 prób. Jaka jest najbardziej optymalna strategia.

PW: A jeśli trafimy, to jaką wiadomość otrzymamy?

Nmn: Przepraszam. Jeśli trafimy, to wygraliśmy, gra zakończona sukcesem.

PW: A jaka może być strategia oprócz − sprawdzenia n₁=75 |(najbliżej środka zbioru możliwych liczb); trafiliśmy − koniec; − na podstawie komunikatu mówiącego, czy 75 jest większa, czy mniejsza, strzelać najbliżej środka przedziału od 0 do 74 albo przedziału od 76 do 150, to znaczy n₂=37 albo n₂=113; trafiliśmy − koniec; − na podstawie komunikatu, czy liczba wybrana w drugim kroku jest większa, czy mniejsza, wybrać odpowiedni przedział i znów celować najbliżej środka itd.

Satan: Czyli możemy zrobić podział: 0 50 100 150 Teraz wybrałbym liczbę 50 lub 100, dzięki temu w maksymalnie dwóch ruchach bym wiedział, w jakim przedzale leży liczba. Trzeci, bądź drugi ruch − w zależności od trafienia − wybrałbym znów którąś środkową liczbę z przedziału, w którym leży ta liczba. Dzięki temu po dwóch/trzech ruchach znam 25−cio liczbowy przedział, w którym leży szukana liczba. A potem to już czyste szczęście. Może ktoś wymyśli coś lepszego

Nmn: Po prostu nie wierzę że takie podejście jest najlepsze. Może istnieje inne, lepsze od niego. Wybieranie liczby środkowej jest bardzo intuicyjne, ale czy na pewno najlepsze?

PW: Najlepsza strategia to taka, przy której szukaną liczbę zamkniemy w najkrótszym przedziale. Trzeba by wykonać obliczenia, np. w jakim przedziale zamknie x po 5 próbach strategia Satana, a w jakim dzielenie na pół. Sprawdź np. dla x=2. Takie strategie to pewnie jakaś poważna teoria, ale nigdy tego nie zgłębiałem. Trzeba by rozpatrywać wszystkie możliwe lokalizacje x i różne decyzje w kolejnych krokach.

Nmn: Strategia Satana jest lepsza dla tego przypadku, wydaje mi się że będzie lepsza od dzielenia na pół.

Pytający: Satan, Twoja strategia nie jest lepsza dla tego przypadku. Według tej strategii po pierwszej próbie mamy szansę 50/151, że ograniczymy się do 50 liczb i 100/151, że ograniczymy się do 100 liczb. Średnio po nietrafieniu w pierwszej próbie ograniczymy się do 50/150*50+100/150*100≈83,33 liczb. Dzieląc po równo średnio po nietrafieniu w pierwszej próbie ograniczymy się do 75/150*75+75/150*75=75 liczb. Można by liczyć to samo po kolejnych próbach i też będzie gorzej. Średnio najwięcej trafimy strategią: w 4 próbach "w środek", a w ostatniej obojętnie.

Nmn: Przyznam że ma to sens. Dziękuję