Question

На доске написаны числа 1, 2, 3, …, 125 . Разрешается стереть любые два числа и написать вместо них остаток от деления суммы этих чисел на 11 . После 124 таких операций на доске осталось одно число. Какое это число?

Answer 1

Так как остаток от деления суммы на число равен остатку от деления на число от суммы остатков деления каждого слагаемого на число 

т.е. в каком бы порядке мы бы не выбирали числа, на доске останется остаток от деления суммы всех данных чисел на число 11, так как после 124 операций все числа будут задействованы и останется только последний остаток.

1+2+3+...125=125*126:2=125*63=7875 дает при делении на 11 остаток 10, поэтому ответ 10

Answer 2

Заметим, что сумма чисел от 1 до 125 равна 125×126/2 = 7875, которая делится на 11 без остатка, так как 11 делит 75 и 7. Таким образом, после каждой операции сумма чисел на доске также будет делиться на 11 без остатка.

Теперь рассмотрим, как изменится остаток при делении суммы на 11 после одной операции. Пусть мы стираем числа a и b, и записываем вместо них остаток от деления a+b на 11, обозначим его через r. Тогда новая сумма чисел на доске будет равна сумме всех чисел, кроме a и b, плюс r. Таким образом, остаток при делении новой суммы на 11 будет равен остатку от деления старой суммы на 11, плюс остаток от деления r на 11.

Таким образом, если мы проведем n операций, то остаток при делении суммы на 11 будет равен остатку от деления начальной суммы на 11, плюс сумма остатков от деления каждой операции на 11. Но так как сумма чисел на доске делится на 11 без остатка, то итоговый остаток также должен быть равен нулю.

Это означает, что сумма остатков от деления каждой операции на 11 должна быть кратна 11. Рассмотрим все возможные комбинации остатков, которые могут получиться после одной операции:

0 = 0 + 0 1 = 0 + 1 2 = 1 + 1 3 = 2 + 1 4 = 3 + 1 5 = 4 + 1 = 2 + 3 6 = 5 + 1 = 3 + 3 7 = 6 + 1 = 3 + 4 8 = 7 + 1 = 4 + 4 9 = 8 + 1 = 4 + 5 10 = 9 + 1 = 5 + 5

Таким образом, сумма двух любых остатков из этого списка также будет принадлежать этому списку. Мы можем проверить, что сумма всех остатков равна 55, и поэтому она кратна 11.

Это означает, что если мы проведем 124 операции, то остаток при делении итоговой суммы на 11 будет равен остатку от деления начальной суммы на 11, плюс сумма остатков от деления каждой операции на 11, которая кратна 11. Таким образом, итоговый остаток также будет кратен 11