Ważymy kulki, poziom hard: rozwiązanie zagadki

https://xpil.eu/vrr

Zanim podam rozwiązanie niedawno opublikowanej zagadki o dwunastu kulkach, najpierw odrobina teorii.

W klasycznej wersji zagadki ("wiemy, czy szukana kulka jest lżejsza czy cięższa") trzy ważenia wystarczyłyby do znalezienia "czarnej owcy" spośród maksymalnie 27 kulek. Obowiązuje tu prosta zasada trysekcji: jednym ważeniem dzielimy zbiór kulek na trzy w miarę równe podzbiory tak długo, aż dotrzemy do wyniku.

Jednak w przypadku naszej zagadki z dwunastoma kulkami dochodzi jeszcze jedna - binarna - niewiadoma: nie wiemy, czy kulka jest lżejsza, czy cięższa od pozostałych. To oznacza, że zamiast 27 kulek możemy użyć maksymalnie połowy tej liczby (czyli 13.5).

Co oznacza w tym przypadku pół kulki?

Oznacza ni mniej ni więcej to, że jeżeli weźmiemy 13 kulek, uda nam się udzielić poprawnej odpowiedzi za każdym razem. Ale jeżeli weźmiemy ich 14, wówczas przy trzech ważeniach gwarantowane jest jedynie znalezienie odpowiedzi na jedno z pytań: "która kulka?", "lżejsza czy cięższa?", ale już niekoniecznie na obydwa na raz. Tak więc przy 14 kulkach może się okazać, że odkryjemy tylko połowę szukanej informacji o "czarnej owcy". Tak właśnie należy rozumieć 13.5.

No dobra, starczy tego teoretyzowania, zobaczmy teraz w jaki sposób poradzić sobie z tymi nieszczęsnymi dwunastoma kulkami.

Zaczniemy od ponumerowania kulek od 1 do 12.

Następnie:

  1. Dzielimy kulki na trzy grupy po cztery kulki: G1:(1,2,3,4), G2:(5,6,7,8), G3(9,10,11,12)
  2. Ważymy [1] G1 i G2 (pierwsze ważenie).
  3. Jeżeli G1 i G2 są jednakowe, dzielimy kulki na grupy: G4:(1,2,3), G5:(9,10,11); jeżeli nie, przechodzimy do punktu 8.
  4. Ważymy G4 i G5 (drugie ważenie). Jeżeli NIE są jednakowe, przechodzimy do punktu 6.
  5. Jeżeli G4 i G5 ważą tyle samo, wówczas kulka 12 jest inna od reszty - ważymy ją z dowolną inną kulką (trzecie ważenie) i wiemy, czy jest lżejsza czy cięższa => KONIEC.
  6. Ważymy kulki 9 i 10 (trzecie ważenie).
  7. Jeżeli kulki 9 i 10 ważą tyle samo, to czarną owcą jest kulka 11 (czy jest lżejsza, czy cięższa stwierdzamy po wyniku ważenia w pkt. 4) => KONIEC. Jeżeli nie, czarną owcą jest kulka cięższa z nich, jeżeli w drugim ważeniu G5 była cięższa, lub lżejsza z nich, jeżeli G5 była lżejsza ==> KONIEC
  8. Dzielimy kulki na dwie grupy: G6:(1, 5, 6), G7:(2, 7, 8)
  9. Ważymy G6 i G7 (drugie ważenie).
  10. Jeżeli G6 i G7 są jednakowe, wówczas czarna owca znajduje się wśród kulek (3, 4). Ważymy 3 i 4 (trzecie ważenie) - czarną owcą jest kulka, która poszła w górę, jeżeli w pierwszym ważeniu G1 poszła w górę, lub kulka, która poszła w dół, jeżeli G1 poszła w dół => KONIEC
  11. Jeżeli G6 i G7 różnią się (najciekawszy wariant), przechodzimy do punktu 12, jeżeli G7 była cięższa lub do punktu 13, jeżeli G7 była lżejsza:
  12. Jeżeli G7 poszła w dół, wówczas albo 1 jest lżejsza pod reszty, albo jedna z (7,8) jest cięższa od reszty. Ważymy 7 i 8 - jeżeli są w równowadze, lżejszą kulką jest 1 (==> KONIEC), jeżeli któraś z nich jest cięższa, to jest ona czarną owcą (==> KONIEC).
  13. Jeżeli G7 poszła w górę, wówczas albo jedna z kulek (5, 6) jest cięższa od reszty, albo 2 jest lżejsza. Ważymy 5 i 6 - jeżeli są w równowadze, czarną owcą jest 2 (==> KONIEC), a jeżeli nie, czarną owcą jest cięższa spośród (5, 6) (==> KONIEC)
[1] Uwaga: w powyższym algorytmie używam (z lenistwa) słowa "ważymy" w sensie "porównujemy masy". Zważyć sensu stricto nie mamy jak 😉

Jak widać metoda jest niebanalna, ale daje gwarancję znalezienia czarnej owcy za każdym razem.

https://xpil.eu/vrr

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.