Разделы 
Дополнительно
Задача по математике - 1923
2019-01-22 
Таня задумала натуральное число $X \leq 100$, а Саша пытается его угадать. Он выбирает пару натуральных чисел $M$ и $N$, меньших 100, и задает вопрос: «Чему равен наибольший общий делитель $X + M$ и $N$?» Докажите, что Саша может угадать Танино число, задав 7 таких вопросов.
Решение:
Узнав наибольший общий делитель чисел $X + 1$ и 2, Саша определит четность $X$. Если $X$ оказалось четным, то второй вопрос будет о наибольшем общем делителе $X + 2$ и 4, а если нечетным, то о наибольшем общем делителе $X + 1$ и 4. Таким образом, Саша узнает остаток от деления $X$ на 4. Вообще, пусть, задав к вопросов $(k \leq 5)$, Саша определил остаток $r_k$ от деления $X$ на $2^k$. Тогда $(k + 1)$-м вопросом он узнает наибольший общий делитель $X + 2^k - r_k и 2^{k+1}$ (заметим, что $0 < 2^k - r_k < 2^{k+1} \leq 64 < 100$). Если $(X + 2^k - r_k, 2^{k+1}) = 2^{k+1}$, то остаток от деления $X$ на $2^{k+1}$ равен $2^k + r_k$, а если $(X + 2^k - r_k, 2^{k+1}) = 2^k$, то этот остаток равен $r_k$.
Итак, задав 6 вопросов, Саша узнает остаток от деления $X$ на 64. Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более 2. Если их все же 2 - скажем, a и $a+64$, то Петя может задать вопрос «Чему равен наибольший общий делитель $X + 3 - r$ и 3?», где $r$ - остаток от деления $a$ на 3. Ясно, что если $X = a$, то ответ - 3, а если $X = a + 64$, то 1. Итак, седьмым вопросом число $X$ определится однозначно.
Замечание. Можно заметить, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа $X$.
Таня задумала натуральное число $X \leq 100$, а Саша пытается его угадать. Он выбирает пару натуральных чисел $M$ и $N$, меньших 100, и задает вопрос: «Чему равен наибольший общий делитель $X + M$ и $N$?» Докажите, что Саша может угадать Танино число, задав 7 таких вопросов.
Решение:
Узнав наибольший общий делитель чисел $X + 1$ и 2, Саша определит четность $X$. Если $X$ оказалось четным, то второй вопрос будет о наибольшем общем делителе $X + 2$ и 4, а если нечетным, то о наибольшем общем делителе $X + 1$ и 4. Таким образом, Саша узнает остаток от деления $X$ на 4. Вообще, пусть, задав к вопросов $(k \leq 5)$, Саша определил остаток $r_k$ от деления $X$ на $2^k$. Тогда $(k + 1)$-м вопросом он узнает наибольший общий делитель $X + 2^k - r_k и 2^{k+1}$ (заметим, что $0 < 2^k - r_k < 2^{k+1} \leq 64 < 100$). Если $(X + 2^k - r_k, 2^{k+1}) = 2^{k+1}$, то остаток от деления $X$ на $2^{k+1}$ равен $2^k + r_k$, а если $(X + 2^k - r_k, 2^{k+1}) = 2^k$, то этот остаток равен $r_k$.
Итак, задав 6 вопросов, Саша узнает остаток от деления $X$ на 64. Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более 2. Если их все же 2 - скажем, a и $a+64$, то Петя может задать вопрос «Чему равен наибольший общий делитель $X + 3 - r$ и 3?», где $r$ - остаток от деления $a$ на 3. Ясно, что если $X = a$, то ответ - 3, а если $X = a + 64$, то 1. Итак, седьмым вопросом число $X$ определится однозначно.
Замечание. Можно заметить, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа $X$.
