Smerfy i Gargamel
: 29 lis 2023, o 21:21
Danych jest \(\displaystyle{ n}\) smerfów, uwięzionych przez Gargamela, oraz \(\displaystyle{ 2n-1}\) ponumerowanych czapeczek. Gargamel zakłada każdemu smerfowi jedną z czapek. Każdy smerf widzi, jakie czapki są na głowach \(\displaystyle{ n-1 }\) smerfów, ale nie widzi, którą czapkę na jego głowę założył Gargamel. Następnie Gargamel pyta każdego smerfa, którą czapkę ma na głowie. Jeśli co najmniej jeden smerf odpowie poprawnie, to wszystkie smerfy zostaną wypuszczone; w przeciwnym razie zostaną zamknięte w zamku Gargamela. Smerfy mogą ustalić strategię wcześniej, ale po założeniu czapeczek nie mogą się ze sobą porozumiewać; nie znają też odpowiedzi innych smerfów. Czy istnieje strategia gwarantująca smerfom wyjście na wolność 