Олимпиадная задача про шляпы
Эта задача — из общешкольной олимпиады по математике в Бразилии. Мы перевели её и теперь предлагаем решить её вам, потому что никто в редакции с ней не справился. А теперь сама задача:
Есть два верных утверждения:
- Буратино всегда врёт.
- Буратино однажды сказал «Все мои шляпы — зелёные».
Какие выводы можно из этого точно сделать?
- у Буратино есть как минимум одна шляпа
- у Буратино есть только одна зелёная шляпа
- у Буратино нет шляп
- у Буратино есть как минимум одна зелёная шляпа
- у Буратино нет зелёных шляп
Обратите внимание на слово «точно»: выводы должны устоять при любой логической проверке в любой ситуации. То есть наши выводы и его ложь не должны логически противоречить друг другу ни при каких мыслимых условиях.
Решение
Чтобы решить эту задачу, нам понадобится математическая логика и знакомые по программированию понятия TRUE (истина) и FALSE (ложь).
То, что Буратино всегда врёт, означает, что любая его фраза на выходе меняет своё значение на противоположное и имеет значение FALSE. А это значит, что вывод, который мы можем сделать, должен иметь значение TRUE: когда Буратино соврёт, он заменит его значение на противоположное и получит FALSE.
Получается, что нам нужно подставить все предположения по очереди в эту фразу и посмотреть, есть ли такие условия, в которых фраза Буратино станет истиной, либо мы сможем легко это опровергнуть.
У Буратино есть как минимум одна шляпа. Если фраза «Все мои шляпы — зелёные» ложная, значит, у Буратино может быть как минимум одна шляпа другого цвета:
✅ (есть как минимум одна шляпа) → (есть синяя шляпа) = TRUE
Получается, что это высказывание может быть правдой, и Буратино, соврав, скажет, что все его шляпы зелёные — то, что нам подходит. При этом мы точно знаем, что это не может быть зелёной шляпой, иначе Буратино скажет правду, а по условиям это невозможно.
Единственное, чем это можно опровергнуть — это фраза «у Буратино нет шляп». Но мы не будем опровергать это высказывание фразой, потому что про неё поговорим отдельно ниже.
У Буратино есть только одна зелёная шляпа. Это высказывание легко опровергнуть, если представить, что у Буратино есть две зелёных шляпы и одна синяя:
❌ (есть только одна зелёная шляпа) → (есть две зелёных шляпы и одна синяя) = FALSE
Это значит, что мы не можем сделать вывод «у Буратино есть только одна зелёная шляпа», потому что может быть ситуация, когда у него будут две зелёных и одна синяя шляпы, и при этом он соврёт, сказав, что все его шляпы зелёные.
У Буратино нет шляп. Это самая сложная часть задачи, и здесь нам понадобится математическая логика. По её законам из ложного посыла может следовать что угодно — как истина, так и ложь. Покажем на примере.
❌ У Буратино нет шляп, поэтому все его шляпы зелёные (как в нашем случае) — это может быть истиной, потому что это то же самое, что сказать «У Буратино 0 шляп зелёного цвета». Это будет правдой, потому что у Буратино 0 шляп и все они зелёные.
❌ У Буратино нет шляп, поэтому все его шляпы красные — это тоже может быть истиной, потому что шляпы, которых нет, могут быть любого цвета.
Получается, что мы из этой фразы можем построить два противоположных, но истинных вывода, а это значит, что исходная фраза — ложная. А раз она ложная, то и в качестве вывода мы не сможем её использовать.
У Буратино есть как минимум одна зелёная шляпа. Это можно опровергнуть, представив, что у Буратино две синих шляпы:
❌(есть как минимум одна зелёная шляпа) → (есть две синих шляпы) = FALSE
Получается, что если Буратино про это соврёт, то наше FALSE превратится в TRUE и Буратино скажет правду, а этого не может быть по условию. Значит, вывод, что у Буратино есть как минимум одна зелёная шляпа, нам не подходит.
У Буратино нет зелёных шляп. Это можно опровергнуть, если представить, что у Буратино есть одна зелёная и одна синяя шляпа:
❌(нет зелёных шляп) → (есть зелёная и синяя шляпы) = FALSE
Значит, это высказывание нам тоже не подходит.
В итоге, из всего перечисленного можно сделать только один вывод, в котором мы точно уверены — у Буратино есть как минимум одна шляпа.