Po ostatnich wyczynach arytmetycznych dziś pora na odświeżenie pewnej starej jak świat zagadki logicznej.
Zagadka brzmi następująco:
Mamy dziewięć kulek. Wyglądają identycznie, ale wiemy, że jedna z nich jest minimalnie lżejsza od pozostałych.
Mamy do dyspozycji wagę. Taką starego typu, szalkową. Położenie po obu stronach wagi takiej samej masy spowoduje, że waga pozostanie w równowadze. Położenie po którejś ze stron czegoś cięższego niż po drugiej stronie powoduje opadnięcie szalki z cięższą zawartością oraz uniesienie szalki lżejszej.
Nie mamy żadnych innych przyrządów do ważenia.
Naszym zadaniem jest znalezienie tej lżejszej kulki w maksymalnie dwóch ważeniach.
Oczywiście zagadka jest tak stara i tak banalna, że każdy z Czytelników zapewne już się rwie do podania wyniku w komentarzu 😉 Dlatego muszę Was dziś rozczarować, ponieważ to tylko rozgrzewka.
Rozwiązanie zagadki jest trywialne: dzielimy grupę dziewięciu kulek na trzy grupy po trzy kulki, następnie kładziemy na wagę grupy 1 i 2 - jeżeli któraś z szalek pójdzie do góry, mamy już tylko trzech kandydatów. A jeżeli nie, to i tak mamy trzech kandydatów: grupę 3.
Trzech kandydatów numerujemy 1, 2, 3 i powtarzamy operację na pojedynczych kulkach.
Prawda, że proste?
To teraz proszę się skupić:
Mamy 12 kulek, wszystkie wyglądają tak samo, ale jedna z nich ma odrobinę inną masę od pozostałych. Mamy też wagę szalkową, identyczną jak ta opisana powyżej. Mamy do dyspozycji maksymalnie trzy ważenia, po których musimy wskazać tę różniącą się od reszty kulkę a także powiedzieć, czy jest ona cięższa czy lżejsza od każdej z pozostałych.
Czas start...
Proszę bardzo:
1) 12 dzielimy po 6 i ważymy. Wybieramy lżejszą szóstkę.
2) Szóstkę dzielimy na 2 trójki. Wybieramy lżejszą trójkę.
3) Z trójki odrzucamy jedną kulkę i porównujemy 2 kulki.
A dlaczego akurat lżejszą? Skąd wiadomo, że jedna z kulek nie jest cięższa?
faktycznie, rozwiązanie jest dobre tylko wtedy gdy wiemy, że kulka jest lżejsza (lub cięższa).
a da się to rozwiązać w 3 ruchach bez informacji o tym czy kulka jest cięższa czy lżejsza?
Da się. I dla 13 kulek też się da, żeby było ciekawiej. Dla 14 już nie. Kombinuj 🙂
1. porównujemy ze sobą dwie partie , po 4 kulki.
jesli równowaga, to „inna” kulka jest w pozostałej czwórce –> 2a, w przeciwnym wypadku –> 2b.
2a. bierzemy 3 kulki z tej nieważonej poprzednio czwórki i porównujemy z 3 kulkami z porównanych wczesniej partii – one wszystkie są „normalne”.
jeśli porównywane trojki ważą tyle samo, to wredna jest pozostawiona kulka –>3a, w przeciwnym wypadku –> 3aa
3a. Porównujemy nieważoną dotąd kulkę z jedną ze sprawdzonych wcześniej kulek i wiemy czy jest lzejsza czy cięższa – KONIEC.
3aa. wiemy że jedna z kulek w trójce jest „inna” wiemy też z poprzedniego ważenia czy jest lżejsza czy cięższa. Załóżmy , że lżejsza.
porównujemy dwie kulki – jeśli jedna poszła do góry to ona jest Inna. Jesli sa w równowadze to ta pozostała jest Inna – lżejsza. KONIEC
2b. robimy następujacą próbę: na jedną szalkę 3 kulki z szalki, , ktora w p1. poszła do góry – nazwijmy je AL,BL,CL plus 1 kulka z szalki, ktora w p1 poszła na dół – nazwijmy ją DC, na drugą szalkę cztery dobre kulki.
Jeśli dobre kulki poszły do góry, to zła – cięższa – jest kulka D – koniec testu.
Jeśli dobre poszły do dołu to w kulkach ABC jest ta inna i jest cięższa –> 3aa – patrz wyżej.
Jeśli równowaga to 3b
3b. zostały 4 kulki – jedna z szalki , która poszla do góry – DL, trzy z szalki, ktora poszła na dół – AC, BC, CC.
ważymy: szalka 1 – kulka AC plus dobra kulka, szalka 2 kulki BC i DL.
jesli równowaga to inna jest kulka CC – cięższa.
jesli szalka 1 do góry to inna jest kulka BC – cięższa.
coś niedobrze bo jak szalka 1 poszła do dolu to nadal nie wiemy czy zła jest AC czy DL
rozbolala mnie głowa 🙁
Blisko! Do 3aa dobrze, od 2b mały błąd.
Proponuję ponumerować kulki od 1 do 12, a także ponumerować kroki algorytmu samymi liczbami, będzie prościej. No i jakiś licznik ważeń w nawiasie, żeby wiedzieć czy coś jeszcze zostało 😉
P.S. Rzuciłeś się na zagadkę w ostatniej chwili, na jutro rano jest zaplanowany wpis z oficjalnym rozwiązaniem i odrobiną matematyki, która za nim stoi 😉
No tak, wystarczyło się wyspać w nocy i obudziłem się z poprawnym rozwiazaniem, ale to już było za późno 🙁