Олимпиадная задача по математике: доказательство выбора числа 600 среди 372 чисел (Принцип Дирихле, Храмцов Д.)

Лемма. Среди любых 13 подряд идущих натуральных чисел можно выбрать не более четырех так, что никакие два из них не различаются на 4, 5 или 9.

Доказательство. Разобьем 13 чисел a , a+1, a+12на 9 групп (из одного или двух чисел) и запишем группы по кругу в следующем порядке: {a+4}, {a,a+9}, {a+5}, {a+1,a+10}, {a+6}, {a+2, a+11},{a+7},{a+3,a+12}, {a+8} . Если выбрано 5 или более чисел, то некоторые два из них окажутся в одной группе или в соседних группах. Однако из двух соседних групп можно выбрать не более одного числа. Лемма доказана.

Отметим 4 средних числа 599, 600, 601, 602, а все остальные числа от 1 до 1200 разобьем на(1200-4)/13=92группы по 13 последовательных чисел (это возможно, так как 598 делится на 13). Из леммы следует, что в группах по 13 чисел можно выбрать не более92· 4=372-4числа требуемым в условии образом. Значит, отмеченные 4 числа выбраны.