Задача 79514

Темы:    [ Последовательности (прочее) ] [ Разбиения на пары и группы; биекции ] [ Доказательство от противного ] [ Индукция (прочее) ]

Сложность: 5 Классы: 8,9,10

Условие

Можно ли выбрать некоторые натуральные числа так, чтобы при любом натуральном значении n хотя бы одно из чисел n, n + 50 было выбрано и хотя бы одно из чисел n, n + 1987 не было выбрано?

Решение

Ответ: нельзя. Допустим, что это возможно. Докажем, что при любом натуральном значении n ровно одно из чисел n, n + 50 выбрано и ровно одно из чисел n, n + 1987 выбрано. Заметим сначала, что числа от n до n + 99 можно разбить на пары вида (k, k + 50). Действительно, объединение таких пар по всем k = n,..., n + 49 есть в точности набор чисел от n до n + 99. Следовательно, и любой набор из 100m подряд идущих натуральных чисел можно разбить на пары такого вида (так как его можно разбить на наборы из ста подряд идущих чисел, а каждый такой набор можно разбить на пары указанного вида). Аналогично доказывается, что любой набор из 2 ^. 1987m подряд идущих натуральных чисел можно разбить на пары вида (k, k + 1987). Следовательно, любой набор из 2 ^. 50 ^. 1987 = 198700 чисел можно разбить как на пары первого вида, так и на пары второго вида. Рассмотрим набор чисел от n до n + 198700 - 1 включительно. В этом наборе ровно 198700 чисел. Следовательно, его можно разбить как на пары вида (k, k + 50), так и на пары вида (k, k + 1987). Так как в каждой паре вида (k, k + 50) хотя бы одно число выбрано, то всего выбранных чисел хотя бы половина. С другой стороны, в каждой паре вида (k, k + 1987) хотя бы одно число не выбрано. Следовательно, всего выбранных чисел не больше половины. Следовательно, их ровно половина, а значит, в каждой паре, на которые разбивался наш набор, ровно одно число выбрано. В частности, в каждой из пар (n, n + 50) и (n, n + 1987) ровно одно число выбрано. Таким образом, при любом натуральном n ровно одно из чисел (n, n + 50) выбрано и ровно одно из чисел (n, n + 1987) выбрано. Пусть n — какое-нибудь выбранное число. Индукцией по k можно показать, что числа вида n + 50k выбраны при чётных k и не выбраны при нечётных. Действительно, база k = 0 выполняется в силу выбора числа n, а шаг индукции следует из доказанного в предыдущем абзаце утверждения. Аналогично, числа вида n + 1987k выбраны при чётных k и не выбраны при нечётных. Рассмотрим число a = n + 50 ^. 1987. С одной стороны, так как число 1987 нечётно, то число a не выбрано. С другой стороны, так как число 50 чётно, то число a выбрано. Полученное противоречие доказывает, что указанным в условии задачи способом числа выбрать нельзя.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	50
Год	1987
вариант
Класс	8
задача
Номер	5