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

Возьмём N−1N-1 пустых бочек и одну с NN единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1N-1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1N-1 переливаний. Ёмкость одинаковых бочек выбирается не меньше NN.

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

Что нужно знать

Применение в задаче

Шаг 1. Возьмём N−1N-1 пустых бочек и одну с NN единицами воды. В конце в каждой должна быть одна единица. Каждая из N−1N-1 изначально пустых бочек должна хотя бы однажды быть получателем воды. Одно переливание имеет только одного получателя, поэтому нужно не меньше N−1N-1 переливаний. Ёмкость одинаковых бочек выбирается не меньше NN.
N=7N=7

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу