Дано: 200 чисел: 1, 2, 3, 4, ..., 200. Выбрано 101 число.
Найти: Доказать, что среди выбранных чисел найдутся два, из которых одно делится на другое.
Решение:
1. Рассмотрим каждое число от 1 до 200 и его разложение на простые множители. Если числа не делятся друг на друга, они должны быть различными степенями чисел, не имеющими общих множителей.
2. Разобьем числа на группы, где в каждой группе числа могут делиться друг на друга. Для этого определим наборы чисел в виде 2^k * m, где m не делится на 2.
Например:
- Число 12 = 2^2 * 3. Поэтому число 12 входит в группу, где числа имеют форму 2^k * 3.
3. Выберем одно число из каждой группы чисел. Если одно из чисел в группе делится на другое, то они будут иметь одну и ту же форму 2^k * m.
4. Определим количество групп. Поскольку мы имеем 200 чисел, максимальная степень 2^k для чисел до 200 — это k ≤ 7 (так как 2^7 = 128). Количество чисел m не делится на 2 и может принимать значения от 1 до 199. Это дает 100 различных групп.
5. Мы выбрали 101 число из 200. По принципу Дирихле, если у нас 101 число и только 100 групп, то по крайней мере одно из чисел будет принадлежать одной группе более одного раза.
6. Таким образом, найдется пара чисел в одной группе, одно из которых делится на другое.
Ответ: Среди выбранных 101 числа найдутся два числа, одно из которых делится на другое.