Олимпиадная задача про робота на числовой прямой для 9–11 класса (Баранов Д. В.)

Заметим, что если 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ⁿ .