Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, II тур дистанционного этапа

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

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

Рассмотрим первую тысячу десятков и разобьем ее на 500 первых десятков и 500 следующих. В первых 500 десятках рассмотрим 499 пар, состоящие из красного числа и зеленого в следующем десятке. Заме тим, что в каждой паре разность зеленого и красного чисел положительна и меньше 20. По принципу Дирихле найдется 20 пар с одинаковой разностью, равной 0 < a< 20. Аналогично, если в первом десятке брать зеленое

число и

красное в следующем десятке, во второй пятисотке десятков найдется 20 пар с одинаковой разностью красного и зеленого, равной 0<a< 20. Тогда, если выбрать в пар из первого десятка пар второго, будет выбрано по а + 6 < 40 чисел каждого цвета, а сумма их разностей (если из красного всегда вычитать зелёное) будет равна 0.