Задача
У Карлсона есть 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 полных банок. Всё варенье из них Карлсон сможет съесть на следующее утро.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь