МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 22 (16 апреля 2016 года). Переаттестация мудрецов

В некотором государстве король регулярно устраивает для своих придворных мудрецов переаттестацию. Он объявляет им правила испытания и даёт час на обдумывание плана действий. Сегодня вы — мудрецы. Докажите королю свою профпригодность!

1.

На каждого из n мудрецов — а) n = 2; б) n любое — надевают колпак одного из заранее объявленных n цветов, а также дают в руки n шарфов тех же цветов. Каждый мудрец видит колпаки остальных, но не видит свой колпак. По команде все мудрецы надевают на себя один из шарфов. Испытание пройдено, если цвет колпака и цвет шарфа совпали хотя бы у одного мудреца.

2.

Король заявил трём своим мудрецам: „У меня есть три белых колпака и два чёрных. Я надену на каждого из вас по колпаку и хочу в течение минуты услышать от каждого цвет надетого колпака. И никаких подсказок друг другу — только цвет своего колпака”.

3.

В клетках доски а) 2×2; б) 8×8 король в каком-то порядке записал числа а) от 1 до 4; б) от 1 до 64. За один ход мудрец может выбрать любое множество клеток на доске и узнать у короля полный (неупорядоченный) список чисел на этих клетках. Король требует от мудреца, чтобы тот указал точное расположение чисел за наименьшее число ходов. За сколько?

4.

Участвуют двое мудрецов. На глазах у первого мудреца король раскладывает монеты в клетки доски а) 2×2; б) 4×4 — в каждую клетку по монете любой стороной. Далее король загадывает одну из монет, показывая на неё мудрецу, который после этого переворачивает любую монету. Затем к доске подходит второй мудрец — он должен указать на монету, которую загадал король.

5.

Докажите, что в предыдущей задаче у мудрецов нет способа договориться в случае доски из трёх клеток.

Дополнительные задачи

6.

Решите задачу 4 для доски 8×8.

7.

Докажите, что задача 4 имеет решение, только если число клеток на доске — степень двойки.

8.

Король объявил условия n мудрецам: „Вы выстроитесь в колонну и каждый будет видеть впереди стоящих. Из колпаков с номерами от 1 до n + 1 один я спрячу, а остальные надену на вас в случайном порядке. Вы по очереди, начиная с последнего (который видит всех), будете выкрикивать числа от 1 до n + 1, не повторяясь. Все, кроме, быть может, одного, должны назвать номер своего колпака”.