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

Проект МЦНМО
при участии
школы 57
Задача 97945
Темы:    [ Доказательство от противного ]
[ Упорядочивание по возрастанию (убыванию) ]
Сложность: 4-
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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


Решение 1

Предположим, что утверждение неверно. Тогда в каждой корзине меньше 100 яблок (иначе можно оставить одну корзину со 100 яблоками) и непустых корзин меньше 100 (иначе можно оставить 100 корзин по 1 яблоку в каждой). Кроме того, корзин, где не менее 10 яблок меньше 10 (иначе можно оставить 10 корзин по 10 яблок). Значит, яблок не больше  91·9 + 9·99 < 2000.· Противоречие.


Решение 2

Упорядочим корзины по убыванию числа яблок. Утверждение неверно тогда и только тогда, когда в n-й корзине не больше  [99/n]  яблок. Поэтому наибольшее число яблок, при котором утверждение неверно, равно  [99/1] + [99/2] + ... + [99/99] = 473.

Замечания

8 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 9
Дата 1987/1988
вариант
Вариант осенний тур, 7-8 класс
Задача
Номер 6

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

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