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

Проект МЦНМО
при участии
школы 57
Задача 64583
Темы:    [ Теория игр (прочее) ]
[ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

Дана клетчатая полоса  1×N.  Двое играют в следующую игру. На очередном ходу первый игрок ставит в одну из свободных клеток крестик, а второй – нолик. Не разрешается ставить в соседние клетки два крестика или два нолика. Проигрывает тот, кто не может сделать ход.
Кто из игроков может всегда выиграть (как бы ни играл его соперник)?

Решение

Пусть  N > 1.  Приведём выигрышную стратегию второго игрока. Первый ход он делает в крайнюю клетку, а дальше ходит как угодно. После k-го хода первого игрока крестики делят полоску не менее чем на k частей, состоящих из пустых клеток и ноликов. Но к этому моменту выставлен лишь  k – 1  нолик, значит, в одной из частей нолика нет, и туда второй игрок может сделать ход. Так как игра когда-нибудь кончится, проиграет первый.


Ответ

При  N = 1  выигрывает первый игрок, при  N > 1  – второй.

Замечания

1. 7 баллов.

2. Задача также предлагалась в Задачнике "Кванта" ("Квант", 2008, №2, зад. М2083).

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

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 4

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

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