Дано:
- 11 различных натуральных чисел, каждое из которых не превышает 20.
Найти:
- Доказать, что из этих чисел можно выбрать два числа, одно из которых делится на другое.
Решение:
1. Рассмотрим числа от 1 до 20. Все числа можно представить как произведение их простых делителей. Например, 12 = 2^2 * 3, 15 = 3 * 5, и так далее.
2. Мы будем использовать принцип Дирихле. Основная идея заключается в том, что если у нас есть больше объектов, чем ящиков, то хотя бы один ящик содержит больше одного объекта.
3. Разделим числа от 1 до 20 на группы по степени двойки. Рассмотрим следующие группы:
- Группа 1 (2^0): числа, которые делятся на 1, т.е., 1, 3, 5, 7, 9, 11, 13, 15, 17, 19.
- Группа 2 (2^1): числа, которые делятся на 2, т.е., 2, 6, 10, 14, 18.
- Группа 4 (2^2): числа, которые делятся на 4, т.е., 4, 12, 20.
- Группа 8 (2^3): числа, которые делятся на 8, т.е., 8, 16.
- Группа 16 (2^4): числа, которые делятся на 16, т.е., 16.
4. Подсчитаем, сколько чисел попадает в каждую из этих групп:
- Группа 1: 10 чисел
- Группа 2: 5 чисел
- Группа 4: 3 числа
- Группа 8: 2 числа
- Группа 16: 1 число
5. В данной задаче у нас 11 чисел, которые мы хотим разделить по вышеуказанным группам. Обратите внимание, что у нас есть 11 чисел и 5 групп.
6. Для каждой группы чисел, принадлежащих одной и той же группе, одно число обязательно делится на другое, если у нас есть числа с разными степенями двойки.
7. Применим принцип Дирихле: если мы выбираем 11 чисел из 20 и каждый раз будем использовать группы по степени двойки, то в одной из групп обязательно окажется как минимум два числа, одно из которых делится на другое.
Ответ:
Да, из 11 различных чисел, не превышающих 20, можно выбрать два числа, одно из которых делится на другое.