Чрезвычайно красивая задача от Н. Агаханова

[Ktina]

Не смогла удержаться, публикую.

Пусть $a_1, a_2, \dots , a_{10}$ — (попарно — прим. ред.) различные натуральные числа, не меньшие 2, сумма которых равна 678. Может ли сумма остатков от деления некоторого натурального числа $n$ на 20 чисел $a_1, a_2, \dots , a_{10}, 2a_1, 2a_2, \dots , 2a_{10}$ равняться 2012?

Изменится ли ответ, если убрать условие "не меньшие 2"?

[Cash]

Легко вывести, что если при делении числа $N$на $a_i$ получается остаток $r_i$, то при делении на $2a_i$ остаток будет равным или $r_i$ или $r_i+a_i$.
Поскольку $r_i \leqslant a_i-1$, то просуммировав получим, что
$\sum_{j=1}^{20} r_j \leqslant 678 \cdot 3-20=2014$.
Максимум достигается, если $\forall i$ $2a_i|N+1$
А мы должны уменьшить максимум на 2.
Это можно сделать либо уменьшив остаток при делении на 4 (тогда $a_1 =2$) c 3 до 1, либо уменьшив на единичку остатки при делении на $a_1$ и $2a_1$.
В первом случае, среди $a_i$ кроме $a_1=2$ есть еще хотя бы одно четное $2m$. И поскольку при делении на $4m$ должен быть остаток $4m-1$, то $N \equiv 3 \pmod 4$. Противоречие.
Во втором случае - с одной стороны $N$ должно быть нечетным (при делении на $2a_i$ остаток равен $2a_i-1$),
с другой стороны при делении на $2a_1$ остаток равен $2a_1-2$.

-- Ср апр 10, 2013 10:49:27 --

(Оффтоп)

Наверное, это какое-то "левое" решение, т.к. не то что чрезвычайной, но и обычной красоты здесь не вижу