O Pawle i Gawle w więzieniu

Paweł i Gaweł, odsiadujący karę za domową awanturę, dzielili ciasną celę w więzienu przeznaczonym dla N osób. Był piękny, słoneczny poranek. Kiedy wszyscy więźniowie, jak co dzień, spotkali się na spacerniaku, naczelnik zarządził zbiórkę w szeregu i odezwał się w te słowa:

• Stoicie przed ogromną szansą. Możecie już dziś wszyscy opuścić więzienie. Wieczorem każdemu z was zostanie na czole odciścięty numer: liczba całkowita z zakresu od 0 do N-1. Liczby te będą mogły powtarzać się. Opuścicie więzienie, gdy co najmniej jeden z was odgadnie, jaki numer ma na czole. Możecie ustalić wspólną strategię, ale jedynymi informacjami, z jakich możecie korzystać, są liczby widoczne na czołach współwięźniów. Jeżeli którykolwiek z was udzieli innemu nielegalnej informacji, to szansa przepadnie. Odpowiedzi udzielać będziecie równoczeście, pisząc liczbę na kartce, więc żadna strategia, która wykorzystuje odpowiedzi innych, nie wchodzi w grę. Nie zawiedźcie mnie. Jeżeli wam się nie uda, to wszyscy zostaniecie tutaj.

Zadanie: Podaj strategię, która gwarantuje, że więźniowie zostaną uwolnieni lub udowodnij, że taka strategia nie istnieje.

Uściślenia: * w więzieniu jest dokładnie N więźniów

Znalazłem tę zagadkę na zkserowanym fragmencie kartki, nie wiem skąd pochodzi

Rozwiązanie słowno-muzyczne

Formalny dowód poprawności rozwiązania