Олимпиада имени Леонарда Эйлера2009-2010 учебный год, II тур регионального этапа

При каком наибольшем $n$ можно раскрасить числа $1, 2, \dots , 14$ в красный и синий цвета так, чтобы для любого числа $k = 1, 2, \dots , n $ нашлись пара синих чисел, разность между которыми равна $k$, и пара красных чисел, разность между которыми тоже равна $k$? ( Д. Храмцов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. $n = 11$.
Решение. Очевидно, $n \leq 12$, поскольку существует лишь одна пара чисел с разностью 13. Предположим, что требуемое возможно при $n = 12$. Число 12 представляется в виде разности чисел от 1 до 14 ровно двумя способами: $13-1$ и $14-2$. Пусть для определенности число 1 — красное. Тогда число 13 тоже красное, а числа 2 и 14 — синие. Далее, существуют три пары с разностью 11: $12-1$, $13-2$, $14-3$ Пара 13 и 2 разноцветная, значит, две остальных — одноцветные, поэтому число 12 красное (как и 1), а число 3 — синее. Продолжая таким образом рассматривать разности 10, 9, 8 и 7, на каждом шаге мы будем получать, что все возможные пары, кроме двух, уже разноцветные, и поэтому цвета еще двух чисел восстанавливаются однозначно. В итоге мы получим, что числа от 2 до 7 включительно — синие, а числа от 8 до 13 — красные. Но в таком случае число 6 не представляется в виде разности ни красных, ни синих чисел — противоречие. Следовательно, $n \leq 11$. Осталось показать, что $n$ может равняться 11. Один из примеров выглядит так: числа 1, 2, 4, 6, 8, 10, 12 — красные, а числа 14, 13, 11, 9, 7, 5, 3 — синие (расположение синих и красных чисел симметрично относительно середины отрезка $[1, 14]$). Есть и другие примеры.