C, PHP, VB, .NET

Задачата за трите съда е много класическа главоблъсканица. Тя гласи следното:

Задача. Дадени са ви три туби с вместимости съответно 8л., 5л. и 3л. Най-голямата туба е пълна с вода, а другите две са празни. Разделете водата на две равни части по 4л., като за целта може да използвате само тези три съда и да преливате от един в друг без да разливате течност.

Стандартно хората подхождат към решението на задачата чрез метода "проба-грешка". Съответно правят поредица от "завъртания в кръг" докато открият правилен път към решението. Приятелят ми Асен Велчев преди 4 години предложи вариант за решение на задачата чрез използване на проективна координатна система (и ме въвлече като съавтор в негова публикация). Сега ще се опитам да ви покажа този метод по възможно най-достъпен начин. Отворете следната графика в нов прозорец:

На чертежа виждате клетки (правоъгълничета) с координати в тях. Първата координата показва количеството течност в най-голямата туба (от 0 до 8 литра), втората координата - във втората туба (от 0 до 5 литра) и третата координата - в третата туба (от 0 до 3 литра). Важната връзка за тези координати е, че във всеки правоъгълник сборът от координатите е 8, което е количеството течност, което имаме в началото.

Линиите, показани на графиката, са възможни направления, по които можем да се „движим“ (да преливаме). С други думи, можем да преливаме или по хоризонтала, или по диагонал – това са и „осите“ на нашата координатна система – X, Y и Z. Друго важно правило е, че когато поемем в дадена посока, ние сме длъжни да вървим (преливаме) буквално до „края“, т.е. докато достигнем клетка, която е „последна възможна“ в това направление – ръб или връх на въображаемия успоредник, образуван от най-външните клетки. Това е така, защото не можем да отмерваме междинно количество прелята течност: изливаме съдържание от една туба в друга или докато първата туба се изпразни, или до запълване на втората.

По условие, началното състояние представяме с клетка (8, 0, 0). Желаем да се придвижим до желаното състояние: клетка (4, 4, 0). Ето как би изглеждал един възможен път (червените линии):

Преведено с човешки език, това ще звучи така:

1. От голямата туба пресипваме в най-малката, т.е. от състояние (8, 0, 0) преминаваме в (5, 0, 3);
2. Малката туба преливаме в средната: (5, 0, 3) -> (5, 3, 0);
3. От голямата туба пресипваме в малката: (5, 3, 0) -> (2, 3, 3);
4. От малката доливаме средната: (2, 3, 3) -> (2, 5, 1);
5. Изсипваме средната в голямата: (2, 5, 1) -> (7, 0, 1);
6. Изсипваме малката в средната: (7, 0, 1) -> (7, 1, 0);
7. Пресипваме от голямата в малката: (7, 1, 0) -> (4, 1, 3);
8. Изсипваме малката в средната: (4, 1, 3) -> (4, 4, 0).

Лесно е да се намерят всички възможни разумни (нециклещи) решения. Например, до желаното състояние (4, 4, 0) може да се достигне само от две места – (4, 1, 3) или (1, 4, 3). Това са краища на поне два от възможните пътища. До т. (4, 1, 3), изключвайки връщането назад (то би създало цикъл) може да се достигне единствено от (7, 1, 0). И т.н. По този начин се конструират всички възможни пътища. Може да извършите и друго важно наблюдение – от „ъглова“ клетка може да се поеме по три възможни пътя, а от клетка на ръб – по два. При положение, че сме поели по даден път и не желаем да правим цикли, се оказва, че достигайки клетка, която не е връх, имаме само един единствен възможен „разумен път“: за продължение. Колкото до „ъгловите клетки“ – изключвайки връщането назад, имаме две възможни продължения. Тоест, вижда се, че възможните „разумни пътища“ не са толкова много.

Предимството на този метод за решение е очевиден – човек вече не налучква решението на случаен принцип, а получава визуално възприятие, чрез което пътя се намира целенасочено и сравнително лесно (най-добре стартирайки от крайната точка и връщайки се назад). Така задачата се решава по-бързо – човек не гледа коя туба колко литра събира, а може да реши задачата чрез правене на път, прокарвайки маршрут от линийки върху лист хартия. Допълнителен бонус представляват и очевидните невъзможни ситуации. Например, ако някой преформулира задачата, като изиска от вас да започнете от (8, 0, 0) и да отмерите точно (4, 2, 2) – това е невъзможно, защото (4, 2, 2) е вътрешна клетка и тя няма как да бъде достигната. Не на последно място – условието на задачата може да се модифицира безпроблемно така, че да започнете от която и да е клетка. Естествено, не сте ограничени и до 8, 5 и 3 литрови туби – можете спокойно да моделирате произволни задачи и комбинации по описания метод.

П.П. Вторият маршрут, по който се връщаме от (4, 4, 0) към (1, 4, 3), е по-оптимален – в него се достига до началото със 7 преливания.  Намерете този маршрут.

Има и още по-интересни задачи. Например „отмерете 4 литра с възможно най-малко преливания“. Ще видите, че това са клетките по линиите X=4 и Y=4. Премахвайки „вътрешните точки“ остават само (4,4,0), (1,4,3) and (4,1,3), които са и възможните решения. Сега тръгвайки от тях назад към условието ще намерите и най-краткия от трите пътя.

Този подход за решение е публикуван в:

Velchev, A.; Petrov, Ph. – „A trial for systematization of methods for generating and solving variations of discrete optimization problems and the three jugs problem as an example“, MASSEE International Congress on Mathematics MICOM, 2009, Proceedings Education, pages from 214 to 221, ISBN 978-9989-646-40-9