Задача
При каком наибольшем n можно раскрасить числа 1, 2, ..., 14 в красный и синий цвета так, чтобы для каждого числа k = 1, 2, ..., n нашлись пара синих чисел, разность между которыми равна k, и пара красных чисел, разность между которыми тоже равна k?
Решение
Оценка. Очевидно, n ≤ 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 ≤ 11.
Пример для n = 11: числа 1, 2, 4, 6, 8, 10, 12 – красные, а остальные числа – синие (расположение синих и красных чисел симметрично относительно середины отрезка [1, 14]).
Ответ
При n = 11.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь