Уравнивание воды в бочках

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Не более N−1N-1 переливаний
  2. Конкретные переливания

    Сначала: Не более N−1N-1 переливаний

  3. Ответ: да

    Сначала: Конкретные переливания

  4. Почему N−2N-2 не всегда достаточно

    Сначала: Ответ: да

  5. Ответ: нет

    Сначала: Почему N−2N-2 не всегда достаточно

  6. Не более N−1N-1 переливаний

    Сначала: Ответ: нет

  7. Почему N−2N-2 не всегда достаточно

    Сначала: Не более N−1N-1 переливаний

  8. Ответ

    Сначала: Почему N−2N-2 не всегда достаточно

Разобранный пример

В нескольких одинаковых бочках налито некоторое количество литров воды (необязательно одинаковое). За один раз можно перелить любое количество воды из одной бочки в другую.

а) Пусть есть четыре бочки, в которых 29, 32, 40, 91 литров. Можно ли не более чем за четыре переливания уравнять количество воды в бочках?

б) Пусть есть семь бочек. Всегда ли можно уравнять количество воды во всех бочках не более чем за пять переливаний?

в) За какое наименьшее количество переливаний можно заведомо уравнять количество воды в 26 бочках?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Пусть среднее количество воды AA. Выбираем бочку с избытком и бочку с недостатком, переливаем минимум избытка и недостатка. После каждого переливания хотя бы одна из них получает ровно AA. Завершённые бочки больше не трогаем. После уравнивания N−1N-1 бочек последняя автоматически уравнена по общей сумме воды.
Шаг 2. В таблице указаны номер бочки-донора, номер получателя и точное количество воды. После этих переливаний все бочки содержат среднее количество; ни одна не переполняется, потому что получатель заполняется только до среднего.
T=((4;1;19);(4;2;16);(4;3;8))\mathcal T=\left(\left(4;1;19\right);\left(4;2;16\right);\left(4;3;8\right)\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Возьмём N−1N-1 пустых бочек и одну с NN единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1N-1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1N-1 переливаний. Ёмкость одинаковых бочек выбирается не меньше NN.
N=7N=7
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. Пусть среднее количество воды AA. Выбираем бочку с избытком и бочку с недостатком, переливаем минимум избытка и недостатка. После каждого переливания хотя бы одна из них получает ровно AA. Завершённые бочки больше не трогаем. После уравнивания N−1N-1 бочек последняя автоматически уравнена по общей сумме воды.
Шаг 2. Возьмём N−1N-1 пустых бочек и одну с NN единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1N-1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1N-1 переливаний. Ёмкость одинаковых бочек выбирается не меньше NN.
N=26N=26
Шаг 3. Записываем найденное значение.
2525

Открыть задачу целиком

Попробовать самостоятельно