Érdekes feladatok

Marton József nemrégiben egy levelet juttatott el hozzánk, amiben többek között két érdekes feladatot küldött, amelyekkel a Bevezetés a számításelméletbe című gyakorlaton találkozott.

1. feladat

Van egy falu, ahol 100 házaspár él és rajtuk kívül még egy varázsló. Minden férj nagyon okos, és ezért a saját feleségén kívül minden asszonyról tudja, hogy hűtlen-e.
A varázsló egy nap azt mondja: a feleségeitek között van hűtlen asszony. Aki rájön arra (teljes biztonsággal), hogy az ő felesége hűtlen, az kongassa meg a következő reggel a harangot. Az első kilencvenkilenc reggelen nem szól a harang. Mi történik a 100-ik reggelen?

(A férjek között ez a téma tabu, és így nem beszélnek róla senkivel.)