|
|
 |
Условие
Капитан Врунгель в своей каюте разложил перетасованную колоду из 52 карт по кругу, оставив одно место свободным. Матрос Фукс с палубы, не отходя от штурвала и не зная начальной раскладки, называет карту. Если эта карта лежит рядом со свободным местом, Врунгель её туда передвигает, не сообщая Фуксу. Иначе ничего не происходит. Потом Фукс называет еще одну карту, и так сколько угодно раз, пока он не скажет “стоп”. Может ли Фукс добиться того, чтобы после слова "стоп"
а) каждая карта наверняка оказалась не там, где была вначале?
б) рядом со свободным местом наверняка не было туза пик?
Решение
a) Вот один из возможных способов. Фукс за 52 тура называет 52² карт – в каждом туре все карты по разу в одном и том же порядке, после чего говорит "стоп". Заметим, что всякий раз карты передвигаются в одном направлении: если передвинута карта a, то следующей будет передвинута карта b по другую сторону от свободного места: она будет названа раньше a. В каждом туре хотя бы одна карта сдвинется, значит, сдвигов не менее 52, и каждая карта со своего места уйдёт. С другой стороны, каждая карта сдвинулась не более 52 раз, поэтому полный круг (53 хода) она сделать не успеет и на свое место не вернётся.
б) Покажем, что для любой стратегии Фукса (последовательности названных карт) есть "проигрышная" исходная позиция, которая в результате перейдёт в позицию с тузом возле свободного места.
Назвав карту повторно, мы "откатываем назад" предыдущий ход. Возьмём любую позицию с тузом возле свободного места. Назвав всю последовательность карт из данной стратегии в обратном порядке, мы "откатаем" эту позицию до требуемой "проигрышной" исходной.
Ответ
a) Может; б) не может.
Замечания
1. В а) есть и другие алгоритмы. Например, Фуксу достаточно назвать все карты в некотором определённом порядке 51 раз.
2. Баллы: 8-9 кл. – 5 + 5, 10-11 кл. – 4 + 4.
