Question

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

Answer 1

Мы берем число, которое получилось после всех нажатий кноп

Пример

23:2=11(ост. 1)

11+1=12

12:2=6

6:3=3

И т.д.

Answer 2

Пусть изначально на экране горит число n.

а) Если число n целое, то рассмотрим последовательность операций, выполненных Васей. Обозначим через L и R нажатия на левую и правую кнопки соответственно. Если Вася выполнил последовательность LRLRLR..., то полученное число будет выглядеть следующим образом:

n → 2n-1 → 2(2n-1)+1 = 4n-1 → 2(4n-1)-1 = 8n-3 → ...

Можно заметить, что каждое четное число в этой последовательности представляется в виде 2^kn-a, где k - количество L в последовательности, n - изначальное число, a - неотрицательное целое число. Также каждое нечетное число представляется в виде 2^kn+a. Таким образом, по финальному числу на экране и изначальному числу n можно однозначно восстановить последовательность нажатий Васи.

б) Если число n произвольное, то анализ последовательности нажатий Васи сложнее. В данном случае, оператору не будет достаточно только числа на экране и изначального числа n для определения порядка нажатий. Таким образом, в общем случае нельзя однозначно определить порядок нажатий Васи на основе только финального числа и изначального числа.

Таким образом, в случае произвольного числа на экране (пункт б) нельзя однозначно определить порядок нажатий Васи, а в случае целого числа на экране (пункт а) оператор сможет определить порядок нажатий.