Числа от 1 до 1000000 разбили на 100000 десятков (то есть групп от 10a+1 до 10a+10) и в каждом десятке покрасили одно число в красный цвет, а другое в зелёный. Докажите, что можно выбрать несколько (не более 50) красных чисел и столько же зелёных чисел так, чтобы сумма выбранных красных чисел была равна сумме выбранных зелёных.

Предположим, что это невозможно. Рассмотрим сумму всех красных чисел и сумму всех зелёных чисел. Обозначим сумму красных чисел как S_r, а сумму зелёных чисел как S_g.

Так как каждое число от 1 до 1000000 встречается ровно один раз в каждом десятке, то сумма всех чисел от 1 до 1000000 равна 500000500000. Это значит, что S_r + S_g = 500000500000.

Если предположить, что сумма выбранных красных чисел не равна сумме выбранных зелёных, то одна из сумм, скажем S_r, будет больше. Без ограничения общности, предположим, что S_r > S_g.

Теперь рассмотрим разность S_r - S_g. Она равна S_r + S_g - 2S_g = 500000500000 - 2S_g = 2(S_r - S_g). Так как S_r > S_g, то разность S_r - S_g > 0, а значит и 2(S_r - S_g) > 0.

Но сумма всех чисел от 1 до 1000000 делится на 2, поэтому 500000500000 делится на 2, что означает, что 2(S_r - S_g) должно делиться на 2. Противоречие.

Следовательно, наше предположение о том, что невозможно выбрать несколько красных и зелёных чисел так, чтобы их суммы были равны, неверно. Таким образом, можно выбрать не более 50 красных чисел и столько же зелёных чисел так, чтобы их суммы были равны.