Объясните решение задания по теории чисел. 98 баллов.

Question

Дан 1 ответ

Правильный ответ

Обозначения:

$a_1, ... , a_n$ - числа которые написаны на доске, при этом условимся что $a_1=1<a_2<...<a_n=1501$ .

$S$ - сумма этих чисел, т.е. $S=a_1+a_2+...+a_n$ .

$a \equiv b \pmod r$ - остаток от деления a на r, равен остатку от деления b на r.

Решение:

Выберим какое-нибудь число на доске - $a_i$ (где $1\leq i \leq n$ ). Тогда, из условия следует что $S-a_i \equiv 0 \pmod{n-1}$ (т.е. $S-a_i$ делится на n-1).

Отюда в частности получаем, $S-1 \equiv 0 \pmod{n-1}$ . Следовательно, $S-a_i = q_1(n-1), \, S-1=q_2(n-1)$ (где, $q_1, q_2$ какие-то натуральные числа), и очевидно что $(q_2-q_1)(n-1)=(S-1)-(S-a_i)=a_i-1$ . Т.е. $a_i-1$ делится на n-1.

Отсюда выводим, $a_i - 1 = q_i(n-1), \,\,q_i\in \mathbb N$ и конечно же, $a_i = q_i(n-1)+1$ . Из-за того что 2" alt="n-1>2" align="absmiddle" class="latex-formula"> (т.к. на доске больше 3 чисел), понятно что выполняется $0\leq 1 < n-1$ . Этот факт, дает нам заключить, что 1 является остатком при делении $a_i$ на $n-1$ (см. Теорема о делении с остатком).

Так как наши выводы не зависят от $i$ , это верно для любого $a_i$ . Проще говоря, каждое число на доске, при делении на n-1 дает остаток 1.

Таким образом, мы нашли необходимое условие для того что-бы условие задачи выполнялось.

Теперь докажем, что это же условие - "каждое число на доске, при делении на n-1 дает остаток 1" - является достаточным условием.

Так как $a_i = q_i(n-1)+1$ то

$S-a_i=a_1+...+a_i+...+a_n-a_i= \\\\=(q_1(n-1)+1)+...+(q_i(n-1)+1)+...+(q_n(n-1)+1)-\\\\-(q_i(n-1)+1)= (q_1+...+q_i+...+q_n)(n-1)+n- (q_i(n-1)+1)=\\\\=(q_1+...+q_i+...+q_n-q_i)(n-1)+n-1=\\\\=(q_1+...+q_{i-1}+q_{i+1}+...+q_n)(n-1)+(n-1)=\\\\=(n-1)(q_1+...+q_{i-1}+q_{i+1}+...+q_n+1)$

т.е. $S-a_i \equiv 0 \pmod{n-1}$ . Ч.Т.Д.

Теперь, мы с легкостью можем ответить на а) и б).

а) Предположим, что 5 написано на доске. Тогда, из необходимого условия, следует что $5-1=q(n-1)$ , т.е. что 4 делится на n-1. Однако, 4 делится только на себя, 2 и 1. Так как, 2" alt="n-1>2" align="absmiddle" class="latex-formula">, то $n-1=4$ т.е. $n=5$ .

Три числа нам уже известны, подберем 2 остальных с помощью достаточного условия - нам нужны числа которые при делении на 4 дают остаток 1. Такие числа, к примеру, могут быть 9 и 17.

Т.е. если на доске написаны к примеру 1, 5, 9, 17 и 1501. То условие задачи выполняется. Следовательно, 5 может быть на доске.

б) Предположим, что 12 написано на доске. Тогда, из необходимого условия следует что 11 делится на n-1. Т.к. 11 простое число и n-1 больше единицы, n-1 обязан быть 11. Т.е. $n=12$ . Однако, из того же условия выводим что 1500 делится на 11, что в корне не верно.

Следовательно, 12 не может быть на доске.

в) Очевидно что для любых двух чисел $a_i < a_j$ (на доске), выполняется - $a_j - a_i=(q_j(n-1)+1) - (q_i(n-1)+1)=(q_j-q_i)(n-1)$ , а также $q_i <q_j$ . Следовательно, 0" alt="q_j-q_i>0" align="absmiddle" class="latex-formula">, что эквивалентно (из-за того что $q_i,q_j$ целые числа) $q_j - q_i\geq 1$ .

Поэтому, $a_j-a_i =(q_j-q_i)(n-1)\geq (n-1)$ , т.е. разности каждых двух чисел должно быть больше или равно (n-1).

Для того что бы найти максимальное n, при котором первое число - 1 и последнее - 1501, нам нужно минимизировать разницу между всеми последовательными числами, т.е. $a_2-a_1, a_3-a_2,...,a_n-a_{n-1}$ . Из неравенства которое мы вывели, следует что максимальная минимизация - $n-1$ .

Т.е., самая большая последовательность чисел на доске будет следующей: $1, 1+(n-1), 1+2(n-1), ...,1+(n-1)(n-1)$ . Однако, в таком случае $1501= 1+(n-1)(n-1)$ , т.е. $1500=(n-1)(n-1)$ , однако 1500 не точный квадрат, поэтому разобьем его на произведение двух чисел, да так, что-бы $n \leq 39$ (т.к. точное решение 1500=(n-1)(n-1) будет $n \approx 39.72$ ). Единственное такое число, которое является максимальным и выполняет данное требование - n = 31. Т.к. 1500 = 50 * 30.

Newtion_zn (46.3k баллов) 01 Июнь, 20