IMO олимпиада по математике 2009 года | Казахстанские олимпиады

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