Question

Натуральні числа від 1 до 2011 пофарбовані у два кольори. Числа 1 і 2011 — червоні, 11 і 20 — сині. Доведіть, що можна обрати пару червоних і пару синіх чисел з однаковими сумами.

Answer 1

Пусть таких чисел не нашлось.

Заметим, что поскольку есть пара красных чисел с суммой 1 + 2011 = 2012, то число 2012 - 11 = 2001 - красное, иначе была бы пара синих чисел с суммой 11 + 2001 = 2012.

Теперь есть еще и красная пара с суммой 1 + 2001 = 2002, тогда 2002 - 11 =  1991 - тоже красное.

Аналогично, появилась пара красных чисел с суммой 1992, тогда и 1992 - 11 = 1981 обязано быть красным.

Повторив указанный выше процесс ещё 178 раз, получим, что число 201 - красное.

Повторяем написанное выше, но уже с синим числом 20. 1 и 201 - красные, тогда 202 - 20 = 182 - красное. Дальше находим, что красными будут и 1 + 182 - 20 = 163, 144, 125, 106, 87, 68, 49, 30 и 11

Исходя из рассуждения 11 должно быть красным, хотя по условию оно синее. Противоречие, исходное предположение неверно, и такие пары чисел найдутся.

Answer 2

Давайте розглянемо можливі пари чисел з однаковими сумами і подивимося, чи можуть вони бути різного кольору:

1. Пари червоних чисел: (1, 2011)
2. Пари синіх чисел: (11, 20)

Зауважте, що найменша можлива сума для пари червоних чисел - 1 + 1 = 2, а найбільша сума для пари синіх чисел - 20 + 20 = 40.

Тепер давайте розглянемо суми можливих пар чисел в діапазоні [2, 40]:

2, 3, 4, ..., 40.

Всього 39 можливих сум. Але у нас є 41 числова пара, яку ми повинні розфарбувати. Згідно принципу Дирихле (принцип складної коробки або принцип лотка з печивом), ми маємо як мінімум одну суму, яку представляють принаймні дві різні пари чисел.

Оскільки нам потрібно вибрати пару червоних і пару синіх чисел, і ми вже маємо дві суми: 2 (1 + 1) та 31 (11 + 20), можна побудувати таку комбінацію:

Сума 2 представлена парами: (1, 1) та (11, 11). Сума 31 представлена парами: (1, 30) та (20, 11).

Отже, ми знайшли пару червоних чисел та пару синіх чисел з однаковими сумами (2 і 31).

Таким чином, ми довели, що можна обрати пару червоних і пару синіх чисел з однаковими сумами в даному наборі чисел від 1 до 2011.