sobota, 7 marca 2015

Czułe słówka

Następująca gra została przedstawiona w pracy Gilmera, Koucky'ego i Saksa :

Bolek i Lolek grają z Tolą w taką oto grę. W pokoju znajduje się $n$ ponumerowanych lampek (są to lampki nocne z szufladkami) oraz fotel, na którym siedzi Tola. Na początku żadna lampka nie świeci się. Do pokoju najpierw wchodzi Bolek (Lolek zostaje za drzwiami). Tola podaje numer lampki, a Bolek zapala ją lub nie zapala. Ten akt powtarza się $n-1$ razy, po czym Tola wstaje z fotela, podchodzi do ostatniej lampki i zapala ją lub nie zapala, a następnie chowa w niej kokardkę. Potem krępuje i knebluje Bolka, sadza go na fotelu i nakłada mu na głowę czarny kaptur. Wtedy do pokoju wchodzi Lolek (komunikacja z Bolkiem niemożliwa). Jego zadaniem jest znaleźć kokardkę zaglądając do jak najmniejszej liczby szufladek, nie większej niż pewna z góry ustalona liczba $k$. Jeżeli mu się to uda, to Bolek zostanie rozwiązany i obaj dostaną od Toli nagrodę. W przeciwnym razie wygrywa Tola (i nagrody nie będzie).

Problem:   Jaka jest najmniejsza wartość liczby $k = f(n)$, przy której Bolek i Lolek mają strategię wygrywającą ?

Nietrudno wykazać, że $f(n) \leqslant \left\lceil\sqrt{n}\right\rceil$. Czy istnieje stała $d>0$ taka, że $f(n)>n^d$ dla dostatecznie dużych $n$? Autorzy gry wykazali, że odpowiedź pozytywna implikuje słynną Hipotezę o Czułości, o której można przeczytać w świetnym artykule przeglądowym: Variations on the Sensitivity Conjecture .