Dziś zagadka dosyć prosta i wyjątkowo nie wymagająca jakiejkolwiek znajomości matematyki. Wystarczy umieć liczyć do pięciu.
Otóż chcemy złapać borsuka, który – burżuj jeden – ma aż pięć nor, przypadkiem leżących w jednej linii. Nory są głębokie, więc każdego dnia jesteśmy w stanie zbadać tylko jedną. Z kolei borsuk – paranoik jeden – każdej nocy opuszcza norę i przeprowadza się do sąsiedniej. Nigdy nie przesuwa się o więcej niż jedną w linii, bo nory daleko od siebie, a borsuk niezbyt szybki – czyli np. z drugiej może przeskoczyć tylko do pierwszej lub trzeciej.
Czy istnieje taka kolejność sprawdzania nor, która zagwarantuje nam złapanie borsuka niezależnie od jego ruchów? Jeśli tak, to jaka? Jeśli nie, to dlaczego?
Komentarze
W base64, z losowymi separatorami pomiędzy kolejnymi numerami nor: MjsyOjQuIDI6MjsgMzsgNCw0OzM6IDI=
Zgadza się, ale można prościej.
No pięknie, a ja próbowałem udowodnić, że borsuk z wyrocznią (albo kwantowo rozmyty) zawsze da radę uciec :>
Przypuszczam, że borsuk kwantowo rozmyty może być złapany i niezłapany jednocześnie;-).
Spodziewałem się, że moje rozwiązanie nie będzie optymalne, ale to, że istnieją 6-elementowe rozwiązania mnie zaskoczyło.
(Tak, napisałem sobie wyszukiwacza :-))
Dobra, chyba nikt już nic nie doda, więc czas na rozwiązanie.
Jak słusznie stwierdził danadam, borsuk jest skazany na porażkę – istnieje wiele sekwencji ruchów gwarantujących jego schwytanie. Najkrótsze z nich wymagają sześciu ruchów, a moja ulubiona jest zaiste genialna w swojej prostocie:
2, 3, 4, 2, 3, 4
Żeby nie trzeba było wierzyć na słowo, przeanalizujmy:
Nasz ruch => możliwe pozycje borsuka przed nocą => po nocy
2 => 1, 3, 4, 5 => 2, 3, 4, 5
3 => 2, 4, 5 => 1, 3, 4, 5
4 => 1, 3, 5 => 2, 4
2 => 4 => 3, 5
3 => 5 => 4
4 => borsuk złapany
Warto dodać, że nadmiar paranoi okazał się tu przeciwskuteczny – gdyby borsuk czasem zostawał w tej samej norze na kolejny dzień, żadna sekwencja gwarantująca jego złapanie by nie istniała…