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

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

Условие

Автор: Мусатов Д.

У Карлсона есть 1000 банок с вареньем. Банки не обязательно одинаковые, но в каждой не больше чем сотая часть всего варенья. На завтрак Карлсон может съесть поровну варенья из любых 100 банок. Докажите, что Карлсон может действовать так, чтобы за некоторое количество завтраков съесть всё варенье.


Решение

  Пусть в данный момент осталось V кг варенья. Назовём непустую банку переполненной, полной или неполной, если в ней соответственно больше, равно или меньше 0,01V варенья. Если Карлсон отъест по c кг из 100 банок, то вес полной банки станет  0,01V – c.  Поэтому тип банок, из которых он ел, не изменится.
  Заметим, что в начале переполненных банок нет. Покажем, как Карлсону действовать, чтобы банки по весу варенья в них друг друга не обгоняли и даже самая тяжёлая банка не становилась переполненной.
  Пусть на данный момент переполненных банок нет и есть ровно k полных банок,  0 ≤ k < 100  (это значит, что есть неполные банки и всего непустых банок больше 100). Пусть также в самой лёгкой неполной банке a кг варенья, а самая тяжёлая из неполных банок на d кг легче полной. Карлсон должен съесть по  c = min{a, d}  из всех полных банок и из  100 – k  самых лёгких неполных. Самая тяжёлая неполная банка станет не более чем полной
(0,01V – d ≤ 0,01V – c),  хотя Карлсон из неё не ел, поэтому обгона по весу и "переполнения" не будет. Неполных банок станет меньше: самая лёгкая опустеет (при  c = a)  или самая тяжелая станет полной (при  c = d).
  Когда неполных банок не будет совсем, останется ровно 100 полных банок. Всё варенье из них Карлсон сможет съесть на следующее утро.

Замечания

1. 8 баллов.

2. Задача была опубликована в Задачнике "Кванта" ("Квант", 2006, №3, задача М2004).

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

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

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

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