Задачи на логику, головоломки, загадки, ребусы - Л О Г О - Р А Й

Принцип Дирихле

Имеется 11 различных натуральных чисел, не больше 20. Докажите, что из них можно выбрать два числа, одно из которых делится на другое.

Ответ:

Возьмем все четные числа среди 11 выбранных и разделим каждое на максимальную степень двойки, чтобы в частном получилось нечетное число. Имеем теперь 11 нечетных чисел меньше 20. Среди них есть равные (всего нечетных чисел 10). Отсюда следует утверждение задачи.