|
|
 |
Условие
Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса – угадать масть как можно большее число раз. Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом. Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем
a) 19 карт;
б) 23 карт?
Решение
а) Первыми двумя рубашками можно "закодировать" масть второй карты, следующими двумя – масть четвёртой и т. д. Когда в колоде остались две карты достаточно закодировать лишь их порядок, что можно сделать при помощи рубашки 35-й карты.Таким образом экстрасенс угадает масти 19 карт.
б) Будем называть 1, 3, 5, ..., 35-ю карты нечётными. Рассмотрим следующие 17 карт: все нечётные карты, кроме первой и предпоследней, и вторую карту. Среди них найдутся пять карт одной масти. Назовём эту масть
основной. Положением первых двух карт колоды помощник может закодировать основную масть. Положением (2k–1)-й и 2k-й карт (для
2 ≤ k ≤ 17) помощник может закодировать масть 2k-й карты. Положением рубашки предпоследней карты помощник может закодировать масти двух последних карт (см. решение п. a).
Экстрасенс должен называть основную масть на каждую из выбранных 17 карт. Тогда он угадает масти хотя бы пяти из этих 17 карт. Кроме того, экстрасенс угадает масти всех чётных карт, кроме второй и последней, а также масти двух последних карт. Всего он угадает масти хотя бы 23 карт.
Ответ
а), б) Мог.
Замечания
Покажем, как экстрасенс мог угадать масти 24 карт.
Первый способ. Достаточно из первых 34 карт угадать масти хотя бы 22 (см. конец решения пункта a). Разделим эти 34 карты, кроме первой, на 11 троек, идущих подряд. Положение первой карты (не входящей ни в одну из троек) будет указывать, каких мастей в первой тройке больше – чёрных или красных. Не уменьшая общности, предположим, что чёрных больше.
Рассмотрим карты первой тройки. Назовём натуральными картами первые две чёрные карты. Оставшуюся карту назовем ненатуральной (она может быть как чёрной, так и красной). Поворотом рубашки каждой из двух натуральных карт помощник покажет, какую из двух мастей чёрного цвета должен называть экстрасенс. Используя эту информацию, экстрасенс угадает масти обеих натуральных карт. Поворотом рубашки ненатуральной карты помощник кодирует цвет, который чаще встречается в следующей тройке. (Заметим, что если красная карта в первой тройке не последняя, то её ненатуральность экстрасенс сможет опознать только после ее открытия.)
Теперь то же самое можно сделать со второй тройкой – при этом экстрасенс угадает в ней две масти из трёх и узнает преобладающий цвет следующей тройки и т. д. Таким образом, он угадает масти всех карт, кроме, быть может, первой карты, и еще 11 карт (по одной в каждой тройке), то есть не менее 24 карт.
Второй способ. Первыми двумя рубашками кодируется масть второй карты, если 24-я карта красная, и третьей, если 24-я карта – чёрная. Экстрасенс называет эту масть и на вторую и на третью карту. Если они одной масти, то он угадывает обе, если же разной – то одну, но при этом узнает цвет 24-й карты. В дальнейшем рубашкой 24-й карты кодируется недостающая информация о ней. Так из трёх карт – 2-й, 3-й и 24-й – угадываются, как минимум, две.
Аналогично угадываются по две из 4-й, 5-й и 25-й карт (используются 3-я и 4-я рубашки); ..., из 22-й, 23-й и 34-й карт. Итого
22 карты + (см. а) 2 последние = 24 карты.
Покажем, как экстрасенс мог угадать масти 26 карт.
Рубашками 1-й и 2-й карт помощник кодирует масть 2-й или 3-й карты, рубашками 3-й и 4-й – масть 4-й или 5-й и т.д. Экстрасенс говорит, что 2-я и 3-я карты имеют ту масть, которую показали 1-я и 2-я, 4-я и 5-я – масть, показанную 3-й и 4-й и т.д. При этом он может случайно угадать обе карты пары (назовём это счастьем) или только одну (и тогда он запоминает, какую именно: первую или вторую). Так он продолжает, пока не произойдёт два несчастья (пусть в последний раз – в паре (2k, 2k + 1)). При каждом из этих несчастий помощник мог выбирать, какую из двух мастей в паре кодировать, и этим передать экстрасенсу любое число d от 0 до 3.
С этого момента (то есть начиная с пары рубашек (2k + 1, 2k + 2)) алгоритм называния мастей видоизменяется. Масть первой карты в очередной паре экстрасенс называет как и прежде, а вот предполагаемую масть второй он получает из закодированной, сдвинув её по кругу на число d (круг мастей: пики-трефы-бубны-червы-пики...). Это правило действует для следующих 18 карт и далее, пока по этому правилу не произойдёт шесть несчастий. (За счет выбора d помощник может гарантировать, что на 18 картах не случится больше шести несчастий. Действительно, для каждой пары одно из четырёх возможных значений сдвига даёт счастье, то есть для 9 пар найдётся d, дающее, как минимум, три счастья.)
Проанализируем ситуацию после этого. Экстрасенс не угадал 9 карт (1-ю и по одной в восьми несчастных парах), при этом открыто не менее 23 карт, то есть в колоде осталось не более 13 карт. Далее, экстрасенс уже запомнил (и еще не использовал) положения (первая или вторая) угаданных карт в шести несчастных парах и положение рубашки последней открытой карты (оно еще тоже не использовано). Это позволяет помощнику закодировать цвета (красная или чёрная) следующих семи карт, а их рубашки в дополнение к цвету кодируют и их масть.
Теперь помощник использует последний трюк: масть одной из следующих семи карт он нарочно кодирует неправильно; при этом экстрасенс совершит последнюю, десятую ошибку. Помощник может это сделать с любой из семи карт любым из трёх способов (показать масть со сдвигом от 1 до 3). Так, ценой ошибки в одной из карт он передаёт экстрасенсу число от 1 до 21. Этим он кодирует цвета следующих четырёх карт (24 < 21), и экстрасенс угадывает их масти по их рубашкам. Масти последних двух карт (то есть их порядок следования) кодируются рубашкой 35-й карты.
Заметим, что если карты закончились раньше, чем пройдены все этапы, то все равно сделано не более 10 ошибок.
