Задача 111340

Темы:    [ Двоичная система счисления ] [ Теория игр (прочее) ]

Сложность: 4 Классы: 9,10,11

Условие

Автор: Баранов Д.В.

Андрей и Борис играют в следующую игру. Изначально на числовой прямой в точке p стоит робот. Сначала Андрей говорит расстояние, на которое должен сместиться робот. Потом Борис выбирает направление, в котором робот смещается на это расстояние, и т.д. При каких p Андрей может добиться того, что за конечное число ходов робот попадет в одну из точек 0 или 1 вне зависимости от действий Бориса?

Решение

Заметим, что если p<0 или p>1 , то Борис выиграет (ему достаточно все время выбирать направление от 1 , тем самым увеличивая расстояние от робота до отрезка).
Докажем, что при p[0,1] Андрей выигрывает тогда и только тогда, когда p= , где m и n целые неотрицательные, а дробь несократима.
Докажем часть "тогда". Пусть на некотором шаге координата робота имеет такой вид и лежит между 0 и 1 . Тогда Андрей назовет число .Борис вынужден будет сместить робота в одну из точек или . Эти точки того же вида , но l<n (т.к. m нечетно). Если n>0 , то эти точки лежат между 0 и 1 . Так как знаменатель рано или поздно станет равным 1, т.е. робот попадет в 0 или 1, то выиграет Андрей.
Докажем часть "только тогда". Пусть на некотором шаге координата x робота не представима в таком виде. Тогда для любого d хотя бы одно из чисел x-d , x+d не имеет такого вида, т.к. иначе их полусумма x тоже имела бы такой вид. Значит, Борис может добиться того, чтобы новая координата робота не представлялась в таком виде. Так как 0 и 1 имеют такой вид, то Борис выиграет.

Ответ

p= , где m и n целые неотрицательные, а дробь несократима, m 2ⁿ .

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	71
Год	2008
вариант
Класс	9
задача
Номер	2