Олимпиада имени Леонарда Эйлера 2019-2020 учебный год, II тур дистанционного этапа

На экране компьютера горит число, а на пульте компьютера есть две кнопки. Нажатие на одну из кнопок переводит число $n$, написанное на экране, в $2n-1,$ а на другую — в $2n+1$. Пока оператор отсутствовал, хулиган Вася подкрался к пульту и произвёл сто несанкционированных нажатий на кнопки. Докажите, что по числу, которое теперь горит на экране, оператор (знающий, сколько раз Вася нажимал на кнопки и какое число было на экране до прихода Васи) сможет определить, в каком порядке Вася нажимал на кнопки, если число, горевшее вначале на экране: а) целое; б) произвольное. ( А. Голованов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Решение. а) Очевидно, после любого нажатия кнопки целое число на экране превращается в нечётное. Пусть после $s$-го нажатия кнопки на экране горит число $m = 2k+1.$ Тогда после $(s+1)$-го нажатия на экране окажется либо число $2(2k+1)-1 = 4k+1,$ либо число $2(2k+1)+1 = 4k+3.$ Эти случаи легко различить, найдя остаток от деления числа на экране на 4. Таким образом, по числу после $(s+1)$-го нажатия мы можем найти как число после $s$-го нажатия, так и кнопку, которую Вася нажимал в $(s+1)$-ый раз. Проделав эту процедуру 99 раз, мы узнаем, в каком порядке Вася нажимал кнопки со второго по 100-ый раз, а также какое число получилось у него после первого нажатия. Зная его и исходное число на экране, мы выясним и то, какую кнопку Вася нажимал в первый раз. б) Заведем у компьютера второй экран, на котором исходно горит число 0. Пусть на первом экране — число $x.$ Легко видеть, что если после $k$ нажатий на втором экране горит число $s,$ то на первом — число $2^k x+s.$ Поэтому если вычесть из итогового числа на первом экране число $2^{100}x,$ то мы получим число на втором экране, по которому восстановим последовательность нажатий кнопок как в пункте а.