Logiczne pytania.

[smiechowiec]

Pewna maszyna zwraca wynik operacji w postaci jednej z 3 liczb 0, 1
lub 2.
Niestety nie wyświetla go na ekranie.
Aby dowiedzieć się jaki to wynik można zadać co najwyżej 4 pytania o
1 lub 2 liczby. Maszyna odpowie 1 jeśli ta to liczba ze zbioru,
natomiast 0 w przeciwnym wypadku.
Wystarczyłyby zadać 2 pytania, gdyby maszyna zawsze odpowiadała
prawidłowo, niestety już wiadomo że maszyna może się 1 raz pomylić w
sesji 4 pytań.
Jakie należy zadać 4 pytania, aby mimo tych ułomności zawsze móc
jednoznacznie wywnioskować jaka liczba jest wynikiem ?

[Gość: grzesiek]

Czy maszyna może odpowiedzieć poprawnie cztery razy, czy musi
się raz pomylić?

[smiechowiec]

> Czy maszyna może odpowiedzieć poprawnie cztery razy, czy musi
> się raz pomylić?
Tak, maszyna może odpowiedzieć poprawnie 4 razy.

[Gość: grzesiek]

To się chyba nie da!

[smiechowiec]

A gdyby liczb było 4 (0, 1, 2, 3) a ilość pytań do zadania
wynosiłaby 5, dał byś radę ?
Zasady te same, maksymalnie 1 pomyłka w 5 odpowiedziach.

[Gość: grzesiek]

A to wtedy dam radę. Najpierw zadaję cztery pytania o układy:
01, 12, 23, 30.
Jeśli nie skłamie ani razu to powinien odpowiedzieć 2xTAK i 2xNIE,
w kolejności (cyklicznej) TAK,TAK,NIE,NIE. Jeśli rzeczywiście
tak odpowie, to już wiadomo, a jeśli nie, to albo będzie 3xTAK+1xNIE,
albo 1xTAK+3xNIE. Wiadomo wówczas że ta pojedyncza odpowiedź (1xCOŚ)
jest nieskłamana, a więc łatwo wymyślić piąte pytanie.

Niestety, ten schemat nie stosuje się do orginalnej wersji zagadki.

[smiechowiec]

A gdyby liczb było 2 (0, 1) a ilość pytań do zadania
wynosiłaby 3, dał byś radę ?
Zasady te same, maksymalnie 1 pomyłka w 3 odpowiedziach.

[Gość: grzesiek]

Wystarczą trzy dowolne pytania, na przykład trzy razy to samo:
czy to jest 0?
jeśli więcej będzie odpowiedzi TAK to zero, jeśli więcej NIE to 1.

[smiechowiec]

Dla 2 liczb wystarczyły Ci 2 + 1 pytań.
Dla 4 liczb wystarczyły Ci 4 + 1 pytań.
Dla 3 liczb nie wystarczyły Ci na razie 3 + 1 pytania.
Czy może istnieje jeszcze jakaś inna kombinacja liczb większych od
2, z tymi samymi zasadami, którą trudno było by Ci ustalić ?
np 5 liczb 6 pytań ?

A teraz problem taki jak poprzednio mamy 16 liczb - szukamy tej
jednej, którą zwróciła maszyna. Mamy do dyspozycji tylko 7 pytań, a
maszyna może pomylić się co najwyżej 1 raz.

[Gość: grzesiek]

Schemat dla 4 liczb i 4+1 pytań działa bez zmian dla dowlnie
większych liczb liczb (chłe chłe).

Wydaje mi się że potrafię udowodnić że dla wersji orginalnej, czyli
3 liczby 4 pytania nie ma rozwiązania.

Z tym 16/7 to jeszcze pomyślę. Twoje pytania sugerują istnienie
jakiejś ogólniejszej teorii, coś jakby dotyczyło to transmisji
informacji w kanale z przekłamaniami, ale założenie o co najwyżej
jednym przekłamaniu trochę się z tym kłóci.

[Gość: grzesiek]

Mam sposób dla przypadków z L liczbami, gdzie L=2^n. Wystarcza
wówczas 2*n+1 pytań. Dla przykładu L=16=2^4, 2*n+1=9 pytań:

1,2) Dwa razy pytam o to samo - o połowę wszystkich:
Czy {0,1,2,3,4,5,6,7}?
jeśli odpowie TAK,NIE, to już go mam, bo wiem że skłamał.
Do odgadnięcia jednej spośród 2^n możliwości bez przekłamań
wystarcza n pytań. Gorsza jest sytuacja gdy odpowie TAK,TAK,
lub NIE,NIE. Wprawdzie wiem w której połówce jest szukana liczba,
ale jeszcze nie mam pewności że nie będzie kłamał w przyszłości.
Zakładam dalej że będzie odpowiadał w sposób dla mnie bardziej
niekorzystny, czyli np. TAK,TAK.

3,4) Wiem że liczba jest w zbiorze 0-7. Pytam dwa razy:
Czy {0,1,2,3}?
Zgodnie z umową odpowiada TAK,TAK.

5,6) Pytam dwa razy:
Czy {0,1}?
Odpowiada TAK,TAK.

7,8) Pytam dwa razy:
Czy 0?
Tym razem gorszym przypadkiem jest TAK,NIE, więc on tak odpowiada.
Wprawdzie nie wiem czy to 0 czy 1, ale wiem że już nie skłamie.

9) Pytam ostatni raz:
Czy 0?
I teraz po odpowiedzi już wiem.

Jeśli liczba L nie jest typu 2^n, to n dobieram w taki sposób, żeby
2^(n-1) < L < 2^n,
i wtedy znowu potrzeba 2*n+1 pytań. Wychodzi stąd że dla L=3
potrzeba 5 pytań, a dla L=16, 9 pytań.

[smiechowiec]

No naprawdę nieźle, jestem pod wrażeniem.
Udało Ci się znaleźć uniwersalną metodę do korekcji pojedynczych
błędów.

>Twoje pytania sugerują istnienie jakiejś ogólniejszej teorii,
>coś jakby dotyczyło to transmisji informacji
>w kanale z przekłamaniami...
Tak, oczywiście kody korekcyjne są używane w praktyce.
Najprostszym jest kod Hamminga, który pozwala na korektę
pojedynczych błędów i na detekcję pary błędów, poprzez sprawdzanie
parzystosci odpowiednich grup bitów.

Jednak wracając do naszego probelmu, powiem, że dla 8 liczb da się
ustalić jednoznacznie szukaną liczbę zadając jedynie 6 pytań, a dla
16 liczb wystarczy zadać 7 pytań.
Dasz radę jeszcze nico zoptmalizować Twój algorytm ?

[Gość: grzesiek]

Przypadek 16 liczb i 7 pytań podpada pod klasyczny kod Hamminga (7,4).
Wypisywanie tych 7 pytań trochę mija się z celem (każde pytanie jest
o osiem liczb), bo wykazywanie że to zadziała jest dość żmudne.
Łatwiej to zobaczyć wiedząc że te 16 liczb można zakodować używając
czterech bitów (cyfr 0,1). Cztery pytania dotyczą każdego z bitów
z osobna, a trzy dodatkowe pytania, w teorii nazywają się one bitami
kontrolnymi, dotyczą sum modulo 2 różnych trójek bitów.

[smiechowiec]

Wydaje mi się że doszedłeś już do rozwiązania.
Czy mógłbyś podać Twoje pytania konkretnie, tzn o które liczby
pytasz w kolejnych siedmiu pytaniach ?
A dla sprawdzenia proponuję test na stronie
bogdan.frumos.com/liar