В нескольких одинаковых бочках налито некоторое количество литров воды (необязательно одинаковое). За один раз можно перелить любое количество воды из одной бочки в другую.
а) Пусть есть четыре бочки, в которых 29, 32, 40, 91 литров. Можно ли не более чем за четыре переливания уравнять количество воды в бочках?
б) Пусть есть семь бочек. Всегда ли можно уравнять количество воды во всех бочках не более чем за пять переливаний?
в) За какое наименьшее количество переливаний можно заведомо уравнять количество воды в 26 бочках?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Пусть среднее количество воды A. Выбираем бочку с избытком и бочку с недостатком, переливаем минимум избытка и недостатка. После каждого переливания хотя бы одна из них получает ровно A. Завершённые бочки больше не трогаем. После уравнивания N−1 бочек последняя автоматически уравнена по общей сумме воды.
Шаг 2. В таблице указаны номер бочки-донора, номер получателя и точное количество воды. После этих переливаний все бочки содержат среднее количество; ни одна не переполняется, потому что получатель заполняется только до среднего.
T=((4;1;19);(4;2;16);(4;3;8))
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Возьмём N−1 пустых бочек и одну с N единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1 переливаний. Ёмкость одинаковых бочек выбирается не меньше N.
N=7
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Пусть среднее количество воды A. Выбираем бочку с избытком и бочку с недостатком, переливаем минимум избытка и недостатка. После каждого переливания хотя бы одна из них получает ровно A. Завершённые бочки больше не трогаем. После уравнивания N−1 бочек последняя автоматически уравнена по общей сумме воды.
Шаг 2. Возьмём N−1 пустых бочек и одну с N единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1 переливаний. Ёмкость одинаковых бочек выбирается не меньше N.