Indukcja Halmosa

[nelcia27]

Witam, mam takie zadanie: W pewnym miasteczku mieszka 345 zamężnych matematyczek. Każda z nich wie w każdej chwili czy mąż innej jest wierny czy nie, nic nie wie jednak o swoim mężu. Prawo tego miasteczka wymaga aby każdy, kto jest w stanie przeprowadzić dowód niewierności swojego partnera, zastrzelił go na specjalnym miejscu straceń tego samego dnia o zachodzie słońca. Każda matematyczka jest absolutnie inteligentna i absolutnie prawomyślna. Pewnego dnia pani burmistrz (jedyna niezamężna w miasteczku) ogłosiła, że w miasteczku są niewierni mężowie. Zakazała porozumiewania się paniom matematyczkom w rzeczonej sprawie, jednocześnie nakazując przeprowadzenie rozumowań dowodowych. W rzeczywistości w miasteczku było 40 niewiernych mężów. Co stanie się w miasteczku po ogłoszeniu pani burmistrz?
Proszę o sprawdzenie mojego rozwiązania:
Bez straty na ogólności rozważań przyjmę, że matematyczki \(\displaystyle{ A_{1} , A _{2}, ..., A_{305}}\) mają mężów wiernych, zaś matematyczki \(\displaystyle{ A _{306}, A _{307}, ..., A_{345}}\) mają niewiernych mężów. Wtedy matematyczki \(\displaystyle{ A_{1} , A _{2}, ..., A_{305}}\) wiedzą o 40 niewiernych mężach, a matematyczki \(\displaystyle{ A _{306}, A _{307}, ..., A_{345}}\) o 39 niewiernych partnerach. Weźmy matematyczkę \(\displaystyle{ A _{306}}\) , która pomyślała:" Zakładam, że mój mąż jest wierny. Wtedy \(\displaystyle{ A _{307}}\) wie o 38 niewiernych i zakłada podobnie, że jej mąż jest wierny (bo on ciągle żyje). Analogicznie dzieje się dla pozostałych \(\displaystyle{ (A _{308}, A _{309}, ..., A_{344})}\) matematyczek. W ten sposób matematyczka \(\displaystyle{ A _{345}}\) nie wie o żadnym niewiernym mężu, czyli natychmiast decyduje się zabić swojego. Ponieważ wszyscy mężowie jeszcze żyją to matematyczka \(\displaystyle{ A _{345}}\) wie o jakimś przypadku niewierności, stąd wynika, że 40 mężów jest niewiernych- w tym mój." Analogiczne rozumowanie przeprowadzają matematyczki \(\displaystyle{ A _{307}, ..., A_{345}}\). Zatem zginie 40 niewiernych.
Dobrze?
Czy może wytłuszczony fragment należy zastąpić następującym: Wtedy \(\displaystyle{ A _{307}}\) wie o 38 niewiernych, ale ma wiedzę podobną do mojej, czyli wie o tym, że jest 39 niewiernych partnerów. Skoro jeszcze nie zabiła swego męża to wie o jakimś niewiernym, o którym nie wiem ja. Zatem mój mąż jest niewierny.
Z góry dziękuję za pomoc

[Medea 2]

Nie ma wytłuszczonego fragmentu, ale pierwszej nocy nie stanie się nic. Część pań wie o czterdziestu niewiernych mężach, reszta o trzydziestu dziewięciu. Wyobraź sobie prostszą sytuację: dziesięć par małżeńskich i tylko jeden zdrajca. Wtedy pierwszej nocy dziewięć żon wie o nim, ale jego żona nie. Pierwszej nocy ta dziesiąta żona zorientuje się, że jest jedyną zdradzaną i zastrzeli małżonka.

A co, gdyby było dwóch zdradzających? Wtedy obie żony myślą, że widzą jedynego zdrajcę (chociaż jest ich dwóch). Pierwszej nocy nic się nie wydarzy, więc domyślą się, dlaczego tak się stało - bo same są zdradzane. Życie dwóch mężczyzn dobiegnie końca dzięki logicznemu rozumowaniu, ale dopiero drugiej nocy.

Spróbuj się zastanowić, co by było, gdyby było pięć zdradzających i pięć wiernych.

[nelcia27]

Wydaje mi się, że pierwszej nocy znów nic się nie stanie, a drugiej nocy zginie 5, ale z drugiej strony dlaczego - wedle mojego rozumowania- żony mające mężów wiernych nie uśmierciły swoich małżonków myśląc, że jest 6 niewiernych?

[Medea 2]

Drugiej nocy nie może zginąć pięciu mężów. Twoje wątpliwości są właściwe. Moim zdaniem drugiej nocy może mieć miejsce morderstwo tylko wtedy, gdy dwóch mężów zdradza. Ich żony wiedzą wzajemnie o zdradach. Jeżeli pierwszej nocy wszyscy przeżyją, to obie się domyślą, dlaczego tak się stanie - bo same są zdradzane.

[nelcia27]

Czyli morderstwo nastąpi piątej nocy i zginie pięciu panów?
A w moim zadaniu morderstwo nastąpi czterdziestej nocy i zginie czterdziestu mężów?

[meursault]

Na mój gust indukcyjnie wygląda to tak (przypadek 2, 3 niewiernych można pominąć, ale go rozpisałem):

Jeżeli 1 mąż jest niewierny, to żona zastrzeli go 1 dnia, wiedząc, że wszyscy inni są wierni, a ktoś musi być niewierny.

Jeżeli 2 mężów jest niewiernych. Z punktu widzenia żony niewiernego tylko 1 mąż zdradza. Jeżeli pierwszego dnia nie zostanie on zastrzelony, oznacza to, że jest dwóch niewiernych, w tym jej (w przeciwnym razie stosujemy rozumowanie dla 1 niewiernego). Drugiego dnia obie żony zabijają swoich mężów.

3 mężów jest niewiernych. Każda ze zdradzanych żon zakłada, że jej mąż jest wierny. Jeżeli po 2 dniach mężowie dwóch pozostałych nie zostaną zabici (nie zajdzie rozumowanie dla dwóch niewiernych), to w zbiorze jest trzech niewiernych. Toteż po 3 dniu wszystkie z nich zabijają swoich mężów.

Załóżmy, że dla n-1 mężów niewiernych w dniu n-1 dojdzie do zabójstwa.

Przy n mężów niewiernych: jeżeli po n-1 dni nie dojdzie do zabójstwa, każda z żon zdradzonych wie, że nie może być tylko n-1 zdradzonych (bo zaszłoby rozumowanie n-1). Wobec tego całkowita liczba zdradzających musi być o 1 i tylko o 1 większa, to jest o jej męża. Toteż zabija go następnego dnia, n, podobnie jak n-1 pozostałych żon.

[nelcia27]

Dzięki wielkie, już wszystko jasne