50-я Международная Математическая OлимпиадаГермания, Бремен, 2009 год

Даны попарно различные целые положительные числа ${{a}_{1}}$, ${{a}_{2}}$, $\ldots $, ${{a}_{n}}$, а также множество $M$, состоящее из $n-1$ целого положительного числа, но не содержащее число $s={{a}_{1}}+{{a}_{2}}+\ldots +{{a}_{n}}$. Кузнечик должен сделать $n$ прыжков вправо по числовой прямой, стартуя из точки с координатой 0. При этом длины его прыжков должны равняться числам ${{a}_{1}}$, ${{a}_{2}}$, $\ldots $, ${{a}_{n}}$, взятым в некотором порядке. Докажите, что этот порядок можно выбрать таким образом, чтобы кузнечик ни разу не приземлился в точке, имеющей координату из множества $M$.

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

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано