Temat: zagadki z * albo **
Ale skoro mowa o indukcji, to chciałbym zaprosić do rozwikłania problemu trochę podobnego do zagadki 4., a konkretnie:
-------- PROBLEM WIĘŹNIA --------
--------------------------------------------
Pewien człowiek został skazany na śmierć. Sędzia ogłosił w niedzielę, że wyrok zostanie wykonany w południe, dowolnego dnia w przeciągu tygodnia (do najbliższej soboty włącznie). Dodatkowo, jak głosił wyrok, skazaniec nie może wiedzieć, którego dnia zostanie stracony - może się o tym dowiedzieć najwcześniej na godzinę przed egzekucją.
Na tak brzmiący wyrok, skazaniec się ucieszył, bo znał się na indukcji i uznał, że nie jest możliwe wykonanie wyroku.
Czy miał rację?
Odp. 1. Nie i (przykładowo) w środę w południe przyszedł kat i go ściął.
Odp. 2. Tak, bo postępując zgodnie z regułami indukcji, gdy oznaczymy przez n liczbę dni pozostałych do następnej niedzieli, to:
W sobotę, czyli gdy n=1, gdyby żył, to by już rano wiedział, że musi zostać właśnie tego dnia stracony, skoro jeszcze żyje, a wyrok musi zostać wykonany najpóźniej w sobotę. Dlatego nie może zginąć w sobotę, bo byłoby to niezgodne z wyrokiem (wiedziałby wcześniej, niż na godzinę przed egzekucją, że tego dnia zginie).
Gdy n>1, to z tego, że następnego dnia (dla n-1) nie może zostać stracony, więzień już rano wie, że musi zginąć tego dnia (n). Czyli na n dni przed niedzielą nie może być ścięty, bo to by było niezgodne z wyrokiem.
Inaczej mówiąc:
- W sobotę nie może zostać stracony, bo dożywając soboty wiedziałby, że to już ostatni możliwy dzień wykonania wyroku i właśnie tego dnia zginie.
- W piątek też nie może zostać stracony, bo wie, że, aby wszystko odbyło się zgodnie z wyrokiem, to nie mógłby zginąć w sobotę, bo by o terminie egzekucji był pewien już w piątek po południu - czyli piątek pozostałby ostatnim dniem, w którym mógłby zostać stracony. Zatem w piątek by od rana wiedział, że tego dnia zginie.
- W czwartek nie może zostać stracony, bo wie, że skoro w piątek nie mogą go ściąć, to czwartek jest ostatnim dniem, gdy to się może stać - a wtedy by o tym też wiedział wcześniej, niż na godzinę przed egzekucją.
- W środę natomiast... :)
--------------
Zadanie brzmi identycznie, jak przy zagadce 4. - uzasadnić, które rozwiązanie jest poprawne.
Michał Janke edytował(a) ten post dnia 07.11.08 o godzinie 01:03
пропозиції роботи
