Разделы 
Дополнительно
Задача по математике - 3416
2019-06-03 
Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (четыре масти, по девять карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты, и т. д. Задача экстрасенса - угадать масть как можно большее число раз.
Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом.
Мог ли экстрасенс так договориться с помощником, когда тот еще не знал порядок карт, чтобы обеспечить угадывание масти не менее чем a) 19 карт; б) 23 карты?
Если вы придумали способ угадывания другого количества карт, большего 19, то тоже напишите.
Решение:
а) Заметим, что угадать 18 карт не составляет труда. Действительно, первыми двумя рубашками помощник может «закодировать» масть второй карты (сопоставив каждой масти один из четырех возможных вариантов расположения двух рубашек), следующими двумя рубашками - масть четвертой и т. д.
Когда в колоде остались две карты, экстрасенс знает, какие они (так как он видел, какие 34 карты вышли), и поэтому помощнику достаточно закодировать лишь порядок, в котором они лежат; это легко сделать при помощи рубашки 35-й карты. Действительно, экстрасенс с помощником могут договориться о том, какая масть считается «старше», после чего помощник может положением 35-й карты указать какая из карт старше - 35-я или 36-я. Таким образом экстрасенс угадает масти 19 карт.
б) Будем называть $1, 3, 5, \cdots, 35$-ю карты нечетными. Рассмотрим следующие 17 карт: все нечетные карты, кроме первой и предпоследней, и вторую карту. По принципу Дирихле (см. факт 1) среди этих семнадцати карт обязательно найдутся пять карт одной масти. Назовем эту масть основной. Положением первых двух карт колоды помощник может закодировать основную масть. Положением $(2k - 1)$-й и $2k$-й карт (для $2 \leq k \leq 17$) помощник может закодировать масть $2k$-й карты. Положением рубашки предпоследней карты помощник может закодировать масти двух последних карт (см. решение пункта «а»).
Экстрасенс должен называть основную масть на каждую из выбранных семнадцати карт. Тогда он угадает масти хотя бы пяти из выбранных семнадцати карт. Кроме того, экстрасенс угадает масти всех четных карт, кроме второй и последней, а также масти двух последних карт. Всего он угадает масти хотя бы 23 карт.
Ответ: а), б) Да, мог.
Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (четыре масти, по девять карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты, и т. д. Задача экстрасенса - угадать масть как можно большее число раз.
Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом.
Мог ли экстрасенс так договориться с помощником, когда тот еще не знал порядок карт, чтобы обеспечить угадывание масти не менее чем a) 19 карт; б) 23 карты?
Если вы придумали способ угадывания другого количества карт, большего 19, то тоже напишите.
Решение:
а) Заметим, что угадать 18 карт не составляет труда. Действительно, первыми двумя рубашками помощник может «закодировать» масть второй карты (сопоставив каждой масти один из четырех возможных вариантов расположения двух рубашек), следующими двумя рубашками - масть четвертой и т. д.
Когда в колоде остались две карты, экстрасенс знает, какие они (так как он видел, какие 34 карты вышли), и поэтому помощнику достаточно закодировать лишь порядок, в котором они лежат; это легко сделать при помощи рубашки 35-й карты. Действительно, экстрасенс с помощником могут договориться о том, какая масть считается «старше», после чего помощник может положением 35-й карты указать какая из карт старше - 35-я или 36-я. Таким образом экстрасенс угадает масти 19 карт.
б) Будем называть $1, 3, 5, \cdots, 35$-ю карты нечетными. Рассмотрим следующие 17 карт: все нечетные карты, кроме первой и предпоследней, и вторую карту. По принципу Дирихле (см. факт 1) среди этих семнадцати карт обязательно найдутся пять карт одной масти. Назовем эту масть основной. Положением первых двух карт колоды помощник может закодировать основную масть. Положением $(2k - 1)$-й и $2k$-й карт (для $2 \leq k \leq 17$) помощник может закодировать масть $2k$-й карты. Положением рубашки предпоследней карты помощник может закодировать масти двух последних карт (см. решение пункта «а»).
Экстрасенс должен называть основную масть на каждую из выбранных семнадцати карт. Тогда он угадает масти хотя бы пяти из выбранных семнадцати карт. Кроме того, экстрасенс угадает масти всех четных карт, кроме второй и последней, а также масти двух последних карт. Всего он угадает масти хотя бы 23 карт.
Ответ: а), б) Да, мог.
