Пазл с проливанием воды - Water pouring puzzle

Начальное состояние стандартной головоломки

Пазлы с проливанием воды (также называемый проблемы с кувшином для воды, проблемы с декантированием^[1]^[2] или же измерительные головоломки) являются классом головоломка с участием конечного набора кувшины для воды известных целое число мощности (в пересчете на жидкая мера Такие как литры или же галлоны Изначально каждый кувшин содержит известный целочисленный объем жидкости, не обязательно равный его вместимости. В головоломках этого типа задается вопрос, сколько этапов перелива воды из одного кувшина в другой (пока либо один кувшин не станет пустым, либо другой не станет полным). необходимо для достижения целевого состояния, определяемого объемом жидкости, который должен присутствовать в каком-либо кувшине или кувшинах.^[3]

К Личность Безу, такие головоломки имеют решение если и только если желаемый объем кратен наибольший общий делитель всех целочисленных объемов кувшинов.

Правила

Это распространенное предположение, высказанное в рамках этих головоломок, что кувшины в головоломке имеют неправильную форму и не имеют маркировки, поэтому невозможно точно измерить любое количество воды, которое не полностью заполняет кувшин. Другие предположения об этих проблемах могут включать в себя то, что нельзя пролить воду и что каждый этап перелива воды из исходного кувшина в целевой кувшин останавливается, когда либо исходный кувшин пуст, либо целевой кувшин полон, в зависимости от того, что произойдет раньше.

Стандартный пример

Стандартный пазл такого типа работает с тремя кувшинами объемом 8, 5 и 3 литра. Первоначально они заполнены на 8, 0 и 0 литров. В целевом состоянии они должны быть наполнены 4, 4 и 0 литрами. Головоломка может быть решена в семь шагов, проходящих через следующую последовательность состояний (обозначенную как тройку в скобках из трех объемов воды в трех кувшинах):

[8,0,0] → [3,5,0] → [3,2,3] → [6,2,0] → [6,0,2] → [1,5,2] → [1,4,3] → [4,4,0].

Коули (1926) пишет, что эта головоломка «восходит к средневековью», и отмечает, что она возникла в Баше Учебник математики 17 века.

Вариант со смесителями и раковинами

Решение головоломки с использованием двух емкостей, крана и слива.

Иногда правила формулируются путем добавления источника (крана) и слива (раковины), которые обеспечивают бесконечное количество дополнительной воды и возможность вылить всю жидкость из любого кувшина в раковину. Наполнение кувшина до краев из-под крана или выливание всего содержимого кувшина в сток - все это считается одним шагом при решении проблемы. Эта версия головоломки была показана в сцене из фильма 1995 года. Крепкий орешек с местью.^[4]

Этот вариант идентичен оригиналу, поскольку третий контейнер, способный вместить содержимое первых двух, математически эквивалентен крану или сливу, способному заполнить или опорожнить оба контейнера. Оптимальное решение может быть легко получено с использованием барицентрического графика в форме бильярда (или математического биллиарда).^[5]

Другой вариант^[6] это когда в одном из кувшинов изначально имеется известный объем воды; В этом случае достижимые объемы либо кратны наибольшему общему делителю между двумя контейнерами от существующего известного объема, либо от нуля. Например, если один кувшин на 8 литров пуст, а другой кувшин на 12 литров содержит 9 литров воды для начала, тогда с источником (кран) и сливом (раковиной) эти два кувшина могут измерять объемы 9 литров, 5 литров, 1 литр, а также 12 литров, 8 литров, 4 литра и 0 литров. Самое простое решение для 5 литров: [9,0] → [9,8] → [12,5]; Самым простым решением для 4 литров является [9,0] → [12,0] → [4,8]. Эти решения визуализируются красными и синими стрелками в Декартово сюжет ниже:

Раствор для 5 литров отображается красным цветом слева, а раствор для 4 литров - синим цветом. Все наклонные линии имеют одинаковый наклон -1, что соответствует переливанию воды из одного кувшина в другой.

Три кувшина

Два решения стандартной головоломки с использованием барицентрический сюжет

Если количество кувшинов равно трем, состояние наполнения после каждого шага можно описать в виде диаграммы барицентрических координат, поскольку сумма всех трех целых чисел остается неизменной на всех этапах.^[7] Следовательно, шаги могут быть визуализированы как своего рода бильярдные движения в (отсеченной) системе координат на треугольной решетке.

Барицентрический график справа дает два решения загадки 8, 5 и 3 л. Желтая область обозначает комбинации, достижимые с кувшинами. Сплошные красные и синие пунктирные пути, начиная с квадрата, показывают текучие переходы. Когда вершина попадает в пунктирный черный треугольник, измеряется 4 L. Еще одна заливка алмаза дает по 4 л в кувшины на 8 и 5 л.

Литература

Коули, Элизабет Б. (1926). «Замечание о линейном диофантовом уравнении». Вопросы и обсуждения. Американский математический ежемесячный журнал. 33 (7): 379–381. Дои:10.2307/2298647. JSTOR 2298647. МИСТЕР 1520987.CS1 maint: ref = harv (связь)
Твиди, М. К. К. (1939). «Графический метод решения тартальских измерительных задач». Математика. Газ. 23 (255). С. 278–282. JSTOR 3606420.
Саксена, Дж. П. (1968). «Стохастическая оптимальная маршрутизация». Unternehmensforschung. 12 (1). С. 173–177. Дои:10.1007 / BF01918326.
Этвуд, Майкл Э .; Полсон, Питер Г. (1976). «Модель процесса решения проблем с кувшином для воды». Cogn. Психол. 8. С. 191–216. Дои:10.1016/0010-0285(76)90023-2.
Рем, Мартин; Чу, Ён Ил (1982). «Программа с фиксированным пространством линейной выходной сложности для задачи трех судов». Sci. Comput. Программа. 2 (2). С. 133–141. Дои:10.1016/0167-6423(82)90011-9.
Томас, Гланффруд П. (1995). «Проблема кувшинов с водой: решения с точки зрения искусственного интеллекта и математики». Математика. Школа. 24 (2). С. 34–37. JSTOR 30215221.
Мюррей-Лассо, М.А. (2003). «Математические головоломки, мощные идеи, алгоритмы и компьютеры в обучении решению проблем». J. Res. Techn. 1 (3). С. 215–234.
Лалчев, Здравко Воутов; Варбанова, Маргарита Генова; Воутова, Ирирна Здравкова (2009). «Геометрический метод Перлмана для решения задач заливки жидкости».
Goetschalckx, Марк (2011). «Маршрутизация единого потока через сеть». Intl. Сер. Операция. Res. & Manag. 161. С. 155–180. Дои:10.1007/978-1-4419-6512-7_6.