Олимпиадная задача о картах экстрасенса: угадывание масти с помощью помощника
Задача
Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса – угадать масть как можно большее число раз. Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом. Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем
a) 19 карт;
б) 23 карт?
Решение
а) Первыми двумя рубашками можно "закодировать" масть второй карты, следующими двумя – масть четвёртой и т. д. Когда в колоде остались две карты достаточно закодировать лишь их порядок, что можно сделать при помощи рубашки 35-й карты.Таким образом экстрасенс угадает масти 19 карт. б) Будем называть 1, 3, 5, ..., 35-ю карты нечётными. Рассмотрим следующие 17 карт: все нечётные карты, кроме первой и предпоследней, и вторую карту. Среди них найдутся пять карт одной масти. Назовём эту масть основной. Положением первых двух карт колоды помощник может закодировать основную масть. Положением (2k–1)-й и 2k-й карт (для 2 ≤ k ≤ 17) помощник может закодировать масть 2k-й карты. Положением рубашки предпоследней карты помощник может закодировать масти двух последних карт (см. решение п. a).
Экстрасенс должен называть основную масть на каждую из выбранных 17 карт. Тогда он угадает масти хотя бы пяти из этих 17 карт. Кроме того, экстрасенс угадает масти всех чётных карт, кроме второй и последней, а также масти двух последних карт. Всего он угадает масти хотя бы 23 карт.
Ответ
а), б) Мог.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь