Задачка по элементарной теории чисел

[AnDe]

Доказать, что из любых двухсот натуральных чисел можно выбрать сто сумма которых делится на 100.
Намекните как решать

Кстати в интернете есть доказательство более сильного факта:
Из любых 2n-1 натуральных чисел можно выбрать n сумма которых делится на n.

[hippie]

Решение состоит из трёх частей:

1) Доказать, что из любых 3 целых чисел можно выбрать 2, сумма которых чётна. (Эта часть очевидна.)
2) Доказать, что из любых 9 целых чисел можно выбрать 5, сумма которых кратна 5. (Можно сделать не очень большим перебором.)
3) Доказать, что если уже доказано, что
из любых $(2n-1)$ целых чисел можно выбрать $n$, сумма которых кратна $n$
и
из любых $(2m-1)$ целых чисел можно выбрать $m$, сумма которых кратна $m,$
то из этого следует, что:
из любых $(2mn-1)$ целых чисел можно выбрать $mn$, сумма которых кратна $mn.$