ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109955
Темы:    [ Выигрышные и проигрышные позиции ]
[ Перебор случаев ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

На концах клетчатой полоски размером 1×101 клеток стоят две фишки: слева – фишка первого игрока, справа – второго. За ход разрешается сдвинуть свою фишку в направлении противоположного края полоски на 1, 2, 3 или 4 клетки. При этом разрешается перепрыгивать через фишку соперника, но запрещается ставить свою фишку на одну клетку с ней. Выигрывает тот, кто первым достигнет противоположного края полоски. Кто выиграет при правильной игре: тот, кто ходит первым, или его соперник?

Решение

Выигрывает первый. Сначала ему надо делать ходы длиной в 4 клетки, пока он не встанет на 45-ю клетку. Теперь очередь хода за вторым. Если он тоже все время делает ходы длины 4, очередной ход приведет его на клетку 57. Тогда первый следующим ходом должен пойти на клетку 48 и после ответа второго сходить так, чтобы между ним и вторым оказалось 3 клетки (легко видеть, что это всегда возможно). После этого второй будет вынужден пойти на 1, 2 или 3 клетки и окажется в итоге правее 49-й клетки. Значит, до финиша ему останется больше 48 клеток, и, чтобы добраться туда, он должен будет сделать не меньше 13 ходов. Первый же находится не левее 49-й клетки, и ему до финиша остается не более 52 клеток, которые он сумеет преодолеть за 13 ходов.

Рассмотрим теперь случай, когда среди 11 первых ходов второго был ход менее, чем на 4 клетки.
Тогда он после 11-го хода окажется более, чем в 56 клетках от цели, и для ее достижения ему понадобится минимум 15 ходов, а первому до цели остается 56 клеток, и он сможет добраться до нее за 15 ходов, даже если второй при встрече вынудит его сделать ход длины 3 вместо хода длины 4.

Ответ

Выигрывает первый.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 4
Класс
Класс 9
задача
Номер 98.4.9.6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .