ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35422
Тема:    [ Доказательство от противного ]
Сложность: 3
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

1000 яблок разложены в несколько корзин. Можно убирать корзины и вынимать яблоки из корзин. Докажите, что можно добиться того, чтобы во всех корзинах стало поровну яблок и общее число оставшихся яблок было не меньше 100.

Подсказка

Рассуждая от противного, оцените количество корзин, в которых вначале было не меньше одного яблока, не меньше двух яблок и т.д.

Решение

Предположим противное. Тогда вначале было меньше 100 корзин, в которых было по крайней мере одно яблоко, иначе мы бы взяли из каждой корзины все яблоки кроме одного, и после этого осталось бы не меньше 100 яблок. Таким же образом, вначале было меньше 50 корзин, в которых было по крайней мере два яблока, иначе мы убрали бы все корзины, где было меньше двух яблок и взяли бы из каждой оставшейся корзины все яблоки кроме двух; после этого осталось бы не меньше 100 яблок. Вообще, если обозначить за Аn число корзин, в которых было по крайней мере n яблок, то Аn меньше 100/n, в частности, при n>99 Аn=0. Подсчитаем теперь общее число яблок, которое было вначале во всех корзинах. Для этого в каждой корзине перенумеруем яблоки, начиная с 1. Число яблок с номером 1 во всех корзинах будет равно А1, число яблок с номером 2 во всех корзинах будет равно А2, и т.д. Таким образом, количество яблок во всех корзинах равно А12+... < 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.

Источники и прецеденты использования

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .