Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ136

Оценка за решение задачи ММ136 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

Конкурсная задача ММ136 (МИ3) (5 баллов)

На столе в открытую лежит 16 карт: 4 туза (считаются за 1 очко), 4 двойки, 4 тройки и 4 четвёрки. Петя и Вася по очереди берут оттуда по одной карте и складывают в отдельную стопку (общую). Выигрывает тот, после чьего хода сумма очков в этой стопке составит 21 очко (или заставивший соперника своим ходом превысить это значение). Петя начинает игру. Кто победит в игре и какой стратегии он должен придерживаться (как реагировать на ходы соперника)?

Решение

Позиция в данной игре запысывается четвёркой чисел (a,b,c,d), каждое из которых не больше четырёх и которые представляют количества взятых, соответственно, тузов, двоек, троек и четвёрок. Таким образом, всё множество позиций можно организовать в виде 4-мерного гиперкуба 5х5х5х5 и ходом увеличение одного из индексов текущей ячейки на единицу.

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

:marathon:mm136.jpg

В позициях, соответствующих перебору, стоят единицы, ведь игрок, пришедший в них, проиграл, значит тот, к кому в данный момент перешла очередь хода - выиграл. В позициях, где сумма a+2b+3c+4d=21, стоят нули, т.к. пришедший туда выигрывает, значит, тот, кому очередь ход перешла, проиграл. Остальные ячейки заполняем рекурсивно по правилу: Если из ячейки можно хотя одним ходом попасть в проигрышную, она - выигрышная, а если же все ходы ведут в выигрышные позиции, она - проигрышная.

Таким образом, начальная позиция (0,0,0,0) - выигрышна. Проанализировав таблицу, можно убедиться, что единственный ход Пети, загоняющий Васю в проигрышную позицию - это взять тройку.

Обсуждение

Как оказалось, задачу можно успешно решить и без построения данной таблицы. Большинство участников использовали принцип дополнения суммы до числа, дающего остаток 1 при делении на 5, с некоторыми оговорками, обусловленными ограниченностью количества карт. Кратко правило формулируется так: на первом ходу Петя берет 3, а затем, он должен оставить число, дающее остаток 1 при делении на 5, а если это невозможно, то число, дающее остаток 3.

Проведя компьютерный анализ игры для других позиций, Сергей Половинкин установил, что Петя выиграет для любого N, не делящегося на 5, кроме N=27.

Награды

За правильное решение задачи Дмитрий Пашуткин, Алексей Волошин, Кирилл Веденский, Анатолий Казмерчук, Евгений Гужавин, Александр Ларин и Владислав Франк получают по 5 призовых баллов. Сергей Половинкин получает 5+2=7 призовых баллов. Николай Дерюгин получает 3 призовых балла.

Эстетическая оценнка задачи 4 балла

Разбор задачи ММ136 подготовил Алексей Извалов


 

 


Страница: [[marathon:problem_136]]

marathon/problem_136.txt · Последние изменения: 2011/06/13 21:46 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006