|
|
 |
Условие
Андрей и Борис играют в следующую игру. Изначально на числовой
прямой в точке 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
2n .
