Завдання про бранців і ковпаки, колір яких потрібно визначити
Прибульці погрожують з'їсти землян, якщо ті не пройдуть їх випробування. Допоможіть полоненим впоратися!
Прибульці спіймали 10 землян. Вони впевнені, що бранці дуже смачні, але біда в тому, що поїдати розумних істот їм заборонено. На жаль, інопланетяни не дуже - то вірять в інтелектуальні здібності невільників, тому придумали для них випробування.
Скориставшись перекладачем, прибульці повідомили землянам наступне: "Вас всіх побудують в один ряд обличчям вперед по зростанню. Ви зможете бачити всіх, хто стоїть перед вами. Озиратися назад або виходити з ладу не можна.
Кожному з вас вдягнуть на голову ковпак чорного або білого кольору в довільному порядку. Вам не скажуть, скільки ковпаків якого кольору. Коли подадуть сигнал, ви повинні будете вгадати колір вашого ковпака. Почнуть із замикаючого ладу і продовжать до попереду стоїть.
Не можна вимовляти інших слів, крім «чорний» і «білий», а також подавати якісь підказки інтонацією, інакше вас тут же з'їдять. Якщо хоча б дев'ять з вас правильно відгадають колпака, всіх пощадять. У вас п'ять хвилин на те, щоб обговорити план, а потім вас побудують, одягнуть ковпаки, і ми почнемо ".
Як діяти землянам, щоб врятуватися?
Замикаючий лад бачить всі ковпаки, але може сказати тільки «чорний» або «білий», одночасно повідомивши всім приховану інформацію. Полоненим невідоме загальне число чорних і білих ковпаків, можливих варіантів більше двох. Зате вони обмежені всього двома версіями, коли мова йде про поняття чітності: число може бути або чітким, або непарним.
Ключ до вирішення завдання такий: бранці домовляються, що перший відповідальний скаже, наприклад, «чорний», якщо буде бачити непарне число чорних ковпаків попереду, і «білий», якщо побачить чітке число чорних ковпаків.
Розберемо приклад з зображення вище. Найвищий бранець 1 бачить попереду три чорні ковпаки. Він говорить вголос «чорний». Це дає всім іншим інформацію про те, що попереду непарне число чорних ковпаків. Перший бранець помилився з кольором свого ковпака, але це не страшно: один раз дозволяється відповісти неправильно.
Полонянка № 2 бачить перед собою непарне число чорних ковпаків. Вона розуміє, що на ній білий, і відповідає вірно. Полонений номер 3 бачить чітке число чорних ковпаків і здогадується, що на ньому чорний ковпак, який бачили два перших бранці.
Полонянка № 4 чує відповідь і розуміє, що їй варто шукати чітке число чорних ковпаків, адже за спиною був чорний, але вона бачить попереду тільки один і робить висновок, що і її ковпак чорного кольору. Бранці 5-9 шукають непарну кількість чорних ковпаків, що вони якраз і бачать, при цьому розуміючи, що на них ковпаки білі. Черга доходить до десятого полоненого. Якщо бранець 9 бачив непарне число чорних ковпаків, це означає лише одне - на бранці № 10 чорний ковпак.
Ось як цей алгоритм буде працювати для будь-якого набору ковпаків. Для першого учасника ймовірність неправильної відповіді - 50%, але інформація про чітність ‑ непарність, яку він повідомить, дозволить іншим полоненим вгадати колір їхнього ковпаку.
Кожен відповідальний почне оцінювати кількість чітких і непарних ковпаків попереду. Якщо підраховане в розумі число не збігається з тим, що він бачить, то його ковпак того ж кольору. Кожен раз в такому випадку наступний відповідальний враховує, що чітність ‑ непарність решти ковпаків тепер змінилася.
Ця загадка - переклад відео TED ‑ Ed.
Показати відповідь
Сховати відповідь