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/2m, где 2m - наибольшая степень двойки,  
 не превосходящая k.  
 Тогда сумма 1+1/2+1/3+...1/99 будет заменена на большую сумму вида  
 1+(1/2+1/2)+(1/4+1/4+1/4+1/4)+...+(1/26+1/26+...+1/26),  
 где дробь 1/2m  
  повторяется в скобке не более 2m  
 раз. Таким образом, получаем, что  
 1+1/2+1/3+...1/99 меньше 7,  
 и 100(1+1/2+1/3+...1/99) меньше 700.
			
Доказательство от противного