Условие
1000 яблок разложены в несколько корзин.
Можно убирать корзины и вынимать яблоки из корзин. Докажите, что
можно добиться того, чтобы во всех корзинах стало поровну яблок и
общее число оставшихся яблок было не меньше 100.
Подсказка
Рассуждая от противного, оцените количество корзин, в которых
вначале было не меньше одного яблока, не меньше двух яблок и т.д.
Решение
Предположим противное. Тогда вначале было меньше 100 корзин, в
которых было по крайней мере одно яблоко, иначе мы бы взяли
из каждой корзины все яблоки кроме одного, и после этого осталось
бы не меньше 100 яблок.
Таким же образом,
вначале было меньше 50 корзин, в
которых было по крайней мере два яблока,
иначе мы убрали бы все корзины, где было меньше двух яблок и взяли
бы из каждой оставшейся корзины все яблоки кроме двух; после этого осталось
бы не меньше 100 яблок.
Вообще,
если обозначить за А
n число корзин,
в которых было по крайней мере n яблок, то
А
n меньше 100/n, в частности, при n>99
А
n=0.
Подсчитаем теперь общее число яблок, которое было вначале во всех
корзинах.
Для этого в каждой корзине перенумеруем яблоки, начиная с 1.
Число яблок с номером 1 во всех корзинах будет равно
А
1,
число яблок с номером 2 во всех корзинах будет равно
А
2, и т.д.
Таким образом, количество яблок во всех корзинах
равно
А
1+А
2+... <
100/1+100/2+100/3+...100/99 =
100(1+1/2+1/3+...1/99).
Докажем, что число
100(1+1/2+1/3+...1/99) меньше 1000, тем самым придем к
противоречию с условием.
В сумме 1+1/2+1/3+...1/99 заменим каждое слагаемое вида
1/k на слагаемое 1/2
m, где 2
m - наибольшая степень двойки,
не превосходящая k.
Тогда сумма 1+1/2+1/3+...1/99 будет заменена на большую сумму вида
1+(1/2+1/2)+(1/4+1/4+1/4+1/4)+...+(1/2
6+1/2
6+...+1/2
6),
где дробь 1/2
m
повторяется в скобке не более 2
m
раз. Таким образом, получаем, что
1+1/2+1/3+...1/99 меньше 7,
и 100(1+1/2+1/3+...1/99) меньше 700.
Источники и прецеденты использования