Математикадан Эйлер олимпиадасы, 2019-2020 оқу жылы, Дистанциялық кезеңнің 2-ші туры

Компьютер экранында сан жанып тұр, ал компьютерді басқару құралында екі батырма бар. Батырманың біріншісін басқанда экранда жазылған $n$ саны $2n-1$ санына, ал екіншісін басқанда $2n+1$ санына айналады. Оператор болмаған кезде, қаскүнем Вася басқару құралын алып, батырмаларды 100 рет басқан. Оператор қайтып оралған кезде, ол экранда жанып тұрған сан бойынша Вася батырмаларды қандай ретпен басқанын анықтай алатынын дәлелдеңіз (оператор Вася келгенге дейін экранда қандай сан болғанын және Вася неше рет басқанын біледі). Есепті екі жағдай үшін шешіңіз:
   а) бастапқыдағы экрандағы жанып тұрған сан — бүтін сан;
   б) бастапқыдағы экрандағы жанып тұрған сан — кез келген сан. ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №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,$ то мы получим число на втором экране, по которому восстановим последовательность нажатий кнопок как в пункте а.