Zagadki logiczne

Przykład 1 Rycerz czy łotr

Na wyspie rycerze zawsze mówią prawdę, a łotrzy zawsze kłamią. Spotykasz dwóch mieszkańców, $A$ i $B$. Mieszkaniec $A$ mówi: „Obaj jesteśmy łotrami”. Kim jest $A$, a kim $B$?

1. Przypadek 1: $A$ jest rycerzem. Wtedy jego wypowiedź jest prawdziwa, czyli obaj są łotrami — w szczególności $A$ jest łotrem. Ale założyliśmy, że jest rycerzem. Sprzeczność, więc ten przypadek odpada.
2. Przypadek 2: $A$ jest łotrem. Wtedy jego wypowiedź jest fałszywa. Sprzeczności na razie nie ma, więc drążę dalej.
3. Zaprzeczam wypowiedź: nieprawda, że obaj są łotrami, czyli przynajmniej jeden z nich łotrem nie jest. To prawo de Morgana — zaprzeczenie koniunkcji jest alternatywą.
4. Wiem już, że $A$ jest łotrem, więc tym „przynajmniej jednym” musi być $\textcolor{#E0453A}{B}$ — czyli $B$ jest rycerzem.
5. Kontrola spójności: $A$ jest łotrem, więc musi kłamać. Powiedział „obaj jesteśmy łotrami”, a naprawdę $B$ jest rycerzem — wypowiedź jest fałszywa ✓
6. Kontrola jednoznaczności: rozpatrzyłem oba możliwe przypadki dla $A$ i jeden z nich odpadł przez sprzeczność. Zostało dokładnie jedno rozwiązanie ✓

Odpowiedź: $A$ jest łotrem, $B$ jest rycerzem.

Zwróć uwagę, że zaprzeczeniem zdania „obaj jesteśmy łotrami” nie jest „obaj jesteśmy rycerzami”. Ten błąd prowadzi tu do odpowiedzi, że obaj są rycerzami — a wtedy $A$ mówiłby prawdę, mówiąc, że jest łotrem.

Przykład 2 Fałszywa moneta w dwóch ważeniach

Masz $\textcolor{#16A06A}{9}$ monet, z których jedna jest lżejsza od pozostałych (wyglądają identycznie). Dysponujesz wagą szalkową bez odważników. Znajdź fałszywą monetę w $\textcolor{#16A06A}{2}$ ważeniach.

1. Waga szalkowa daje trzy możliwe wyniki: przeważa lewa, przeważa prawa albo równowaga. Dlatego dzielę monety na trzy grupy, a nie na pół.
2. Dzielę $9$ monet na trzy grupy po $3$: $G_1$, $G_2$, $G_3$.
3. Ważenie 1: kładę $G_1$ na lewą szalkę, $G_2$ na prawą. Jeśli któraś szalka jest lżejsza — fałszywa moneta jest w tej grupie. Jeśli równowaga — fałszywa jest w $G_3$, która nie brała udziału w ważeniu.
4. Po pierwszym ważeniu zostają $\textcolor{#E0453A}{3}$ podejrzane monety, niezależnie od wyniku.
5. Ważenie 2: z tych trzech kładę jedną na lewą szalkę, drugą na prawą. Jeśli któraś jest lżejsza — to ona. Jeśli równowaga — fałszywa jest ta trzecia, odłożona.
6. Kontrola, że dwa ważenia wystarczają: każde ważenie rozdziela przypadki na trzy, więc dwa ważenia rozróżniają $3 \cdot 3 = \textcolor{#E0453A}{9}$ sytuacji — dokładnie tyle, ile jest monet ✓
7. Kontrola, że dzielenie na pół by nie starczyło: $9$ monet dzielimy po połowie na $4$ i $4$, jedną odkładając; po drugim ważeniu $2$ na $2$ zostałyby wciąż dwie podejrzane monety, więc trzeba by trzeciego ważenia ✓

Odpowiedź: Dzielimy na trzy grupy po trzy, ważymy dwie z nich, a potem powtarzamy ten sam ruch wewnątrz wskazanej trójki.

Ta zagadka ma ładne uogólnienie: przy $n$ ważeniach można znaleźć jedną lżejszą monetę spośród $3^n$. Dla trzech ważeń to już $27$ monet.

Przykład 3 Wilk, koza i kapusta

Przewoźnik ma przeprawić przez rzekę wilka, kozę i kapustę. W łódce mieści się on i najwyżej jeden ładunek. Bez nadzoru wilk zje kozę, a koza zje kapustę. Jak to zrobić?

1. Zauważam, co wolno zostawić razem: wilk i kapusta są bezpieczną parą. Koza jest niebezpieczna w obie strony — nie może zostać ani z wilkiem, ani z kapustą.
2. Wniosek: pierwszym ładunkiem musi być koza, bo tylko jej zabranie zostawia bezpieczną parę na brzegu.
3. Przeprawa 1: wiozę kozę na prawy brzeg. Na lewym zostają wilk i kapusta — bezpiecznie ✓
4. Przeprawa 2: wracam pusty.
5. Przeprawa 3: wiozę wilka na prawy brzeg. Na lewym zostaje sama kapusta.
6. Przeprawa 4: wracam z kozą — bo inaczej wilk zostałby z kozą sam. To jest krok, którego brakuje w większości nieudanych prób.
7. Przeprawa 5: wiozę kapustę na prawy brzeg. Na prawym są wilk i kapusta — bezpiecznie ✓, na lewym zostaje sama koza.
8. Przeprawa 6: wracam pusty.
9. Przeprawa 7: wiozę kozę. Wszyscy są na prawym brzegu.
10. Kontrola bezpieczeństwa: sprawdzam każdy moment, w którym przewoźnik jest na wodzie — po przeprawach 1, 2, 3, 4, 5, 6 na brzegach stoją kolejno {wilk, kapusta}, {wilk, kapusta}, {kapusta} i {koza}, {kapusta} i {wilk}, {koza}, {koza} — w żadnym nie ma zakazanej pary ✓
11. Liczba przepraw: $\textcolor{#E0453A}{7}$.

Odpowiedź: Siedem przepraw: koza tam, pusty z powrotem, wilk tam, koza z powrotem, kapusta tam, pusty z powrotem, koza tam.

Rozwiązanie nie jest jedyne — w krokach 3 i 5 można zamienić wilka z kapustą miejscami i też się uda. Są więc dokładnie dwa rozwiązania siedmioprzeprawowe, symetryczne względem siebie.

Przykład 4 Cztery litry w dzbanach na pięć i trzy

Masz dwa naczynia bez podziałki: na $\textcolor{#16A06A}{5}$ litrów i na $\textcolor{#16A06A}{3}$ litry, oraz nieograniczony dostęp do wody. Odmierz dokładnie $\textcolor{#16A06A}{4}$ litry.

1. Stan opisuję parą $(x, y)$: ile litrów jest w naczyniu pięciolitrowym i ile w trzylitrowym. Start to $(0,0)$.
2. Dozwolone ruchy: napełnić naczynie do pełna, wylać je całe, albo przelać z jednego do drugiego aż jedno się opróżni lub drugie napełni.
3. Krok 1: napełniam pięciolitrowe → $(5, 0)$.
4. Krok 2: przelewam do trzylitrowego, aż będzie pełne. Zmieści $3$, więc w dużym zostaje $5 - 3 = 2$ → $(2, 3)$.
5. Krok 3: wylewam trzylitrowe → $(2, 0)$.
6. Krok 4: przelewam te $2$ litry do trzylitrowego → $(0, 2)$.
7. Krok 5: napełniam pięciolitrowe → $(5, 2)$.
8. Krok 6: przelewam do trzylitrowego. Mieści się w nim jeszcze tylko $3 - 2 = 1$ litr, więc w dużym zostaje $5 - 1 = \textcolor{#E0453A}{4}$ → $(4, 3)$.
9. Kontrola bilansu wody: nalewałem dwa razy po $5$ litrów, czyli $10$; wylałem raz $3$ litry; w naczyniach zostało $4 + 3 = 7$. Zgadza się: $10 - 3 = 7$ ✓
10. Kontrola, że wszystkie stany były osiągalne: żaden krok nie wymagał odmierzenia „na oko” — każdy kończył się pełnym albo pustym naczyniem ✓

Odpowiedź: Sześć kroków; po ostatnim w naczyniu pięciolitrowym są dokładnie $4$ litry.

Ta zagadka ma tło arytmetyczne: da się odmierzyć dokładnie te ilości, które są wielokrotnościami $\text{NWD}(5,3) = 1$ — czyli tu każdą liczbę całkowitą litrów od $0$ do $5$. Gdyby naczynia miały $4$ i $6$ litrów, ich NWD wynosiłby $2$ i nieparzystych ilości nie dałoby się uzyskać wcale.

Przykład 5 Wiek trzech córek

Iloczyn wieków trzech córek wynosi $\textcolor{#16A06A}{36}$, a ich suma jest równa numerowi domu naprzeciwko. Rozmówca odpowiada: „to wciąż za mało, żeby ustalić”. Wtedy pada zdanie: „najstarsza gra na pianinie”. Ile lat mają córki?

1. Wypisuję wszystkie trójki liczb naturalnych o iloczynie $36$, uporządkowane niemalejąco, wraz z sumami:
2. $(1,1,36) \to 38$; $(1,2,18) \to 21$; $(1,3,12) \to 16$; $(1,4,9) \to 14$; $(1,6,6) \to 13$; $(2,2,9) \to 13$; $(2,3,6) \to 11$; $(3,3,4) \to 10$. To komplet — ósemka trójek.
3. Rozmówca zna sumę (widzi numer domu) i mówi, że to mu nie wystarczyło. Gdyby suma odpowiadała tylko jednej trójce, wystarczyłaby — więc suma musi powtarzać się w tabeli.
4. Przeglądam sumy: $38, 21, 16, 14, 13, 11, 10$ — powtarza się wyłącznie $\textcolor{#E0453A}{13}$, przy trójkach $(1,6,6)$ i $(2,2,9)$.
5. Zostały dwie możliwości. Rozstrzyga ostatnia informacja: „najstarsza” oznacza, że najstarsza córka jest jedna.
6. W trójce $(1,6,6)$ najstarsze są dwie sześciolatki — nie ma jednej najstarszej, więc ta możliwość odpada.
7. Zostaje $\textcolor{#E0453A}{(2,2,9)}$: dwie dwulatki i dziewięciolatka.
8. Kontrola iloczynu: $2 \cdot 2 \cdot 9 = 36$ ✓
9. Kontrola sumy: $2 + 2 + 9 = 13$ — zgodnie z ustaleniem ✓
10. Kontrola jednoznaczności: z ośmiu trójek sześć odpadło przez unikalną sumę, a siódma przez brak jednej najstarszej. Została dokładnie jedna ✓

Odpowiedź: Córki mają $2$, $2$ i $9$ lat.

Zdanie o pianinie nie mówi nic o muzyce — mówi, że istnieje jedna najstarsza. To najczystszy przykład na to, że w zagadkach informacją bywa sama struktura wypowiedzi, a nie jej treść.