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

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

Условие

Двое по очереди выписывают на доску натуральные числа от 1 до 1000. Первым ходом первый игрок выписывает на доску число 1. Затем очередным ходом на доску можно выписать либо число 2a , либо число a+1 , если на доске уже написано число a . При этом запрещается выписывать числа, которые уже написаны на доске. Выигрывает тот, кто выпишет на доску число 1000. Кто выигрывает при правильной игре?

Решение

Заметим, что если какой-то из игроков выпишет на доску число 500 или 999 (назовем такой ход проигрышным), то его противник следующим ходом выпишет число 1000 и выиграет.

Какие числа могут быть выписаны на доску до появления чисел 500 и 999?

Во-первых, это все числа от 1 до 499 (их 499).
Во-вторых, это все числа от 502 до 998 (их 497), так как 502 можно получить из числа 251.

Заметим также, что число 501 может получиться только из числа 500. То есть перед появлением числа 500 или 999 будет сделано 499+497=996 непроигрышных ходов. Это означает, что проигрышный ход сделает первый игрок.

Ответ

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

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

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

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

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