|
|
 |
Условие
Таня задумала натуральное число X ≤ 100, а Саша пытается его угадать. Он выбирает пару натуральных чисел M и N, меньших 100, и задаёт вопрос: "Чему равен наибольший общий делитель X + M и N?" Докажите, что Саша может угадать Танино число, задав семь таких вопросов.
Решение
Узнав НОД(X + 1, 2), Саша определит чётность X. Если X оказалось чётным, то второй вопрос будет о НОД(X + 2, 4), а если нечётным, то о
НОД(X + 1, 4). В результате Саша узнает остаток от деления X на 4.
Пусть, задав k ≤ 5 вопросов, Саша определил остаток rk от деления X на 2k. Тогда (k+1)-м вопросом он узнаёт НОД(X + 2k – rk, 2k+1) (заметим, что
0 < 2k – rk ≤ 2k+1 ≤ 64 < 100. Если НОД(X + 2k – rk, 2k+1) = 2k+1, то X ≡ 2k + rk (mod 2k+1), а если НОД(X + 2k – rk, 2k+1) = 2k, то X ≡ rk (mod 2k+1).
Итак, задав шесть вопросов, Саша узнает остаток от деления X на 64.
Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более двух. Если их все же два – a и a + 64, – то Саша узнаёт
НОД(X + 3 – r, 3), где r – остаток от деления a на 3. Если X = a, то этот НОД равен 3, а если X = a + 64, то 1. Итак, седьмым вопросом число X определится однозначно.
Замечания
Заметим, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа X.
