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$.