Районная олимпиада, 2022-2023 учебный год, 9 класс

Дано множество из $n$ целых чисел. Пусть «прыжок» представляет собой операцию, в которой будет выбрано любое $k$ чисел из множества, и к каждому такому числу $a$ из выбранных чисел можно прибавить $b \cdot k$, где $b$ любое целое число (для каждого $a$ выбирается свое $b$). Докажите, что за 3 «прыжка» можно сделать все числа из множества нулями.

Комментарий/решение

Очень классная задача.

Сперва возьмем одно число и превратим его в $n$. Возьмем $n-1$ остальных чисел и пусть у них есть остатки по $n$ как: $a_{1},a_{2},…,a_{n-1}$, прибавим к каждому число $n-1$ столько раз сколько у этого числа остаток по $n$. Получили что все числа теперь делятся на $n$, выберем все числа и отнимем $n$ столько раз что бы все числа стали 0.