|
|
 |
Условие
Доказать, что из 17 различных натуральных чисел либо найдутся пять таких чисел a, b, c, d, e, что каждое из чисел этой пятёрки, кроме последнего, делится на число, стоящее за ним, либо найдутся пять таких чисел, что ни одно из них не делится на другое.
Решение
Расставим все числа в последовательность в порядке их возрастания. Пройдём по этой последовательности слева направо и присвоим каждому её элементу числовой индекс следующим образом: индекс числа равен максимальному из индексов его делителей плюс 1 (если у числа делителей нет, то его индекс равен 1). К моменту, когда мы доходим до некоторого числа n, индексы всем его делителям (они могут стоять только слева от n) уже присвоены, поэтому процедура определена корректно. Возможны два случая.
1) В последовательности встретилось число, имеющее индекс 5. Тогда у этого числа есть делитель с индексом 4, у того, в свою очередь, есть делитель с индексом 3, и т. д. Получим пятёрку чисел, в которой каждое следующее делится на предыдущее.
2) Все числа в последовательности имеют индексы меньше 5. Тогда по принципу Дирихле хотя бы один из индексов встретится не менее пяти раз. Но если два числа имеют одинаковый индекс, то ни одно из них не делится на другое.
Замечания
1. Задача предлагалась в "трудном" варианте второго тура.
2. 18 баллов.
