Об алгоритме и постановках задач на переливание жидкости

[Утундрий]

Метод треугольника полезен, ежели сосудов (внезапно!) три. Когда их четыре, можно попытаться, конечно, порисовать пути в пирамиде, но мало у кого имеется настолько развитое пространственное воображение. Так что алгоритмы рулят.

[Munin]

Вообще-то с четырьмя это даёт ещё большее упрощение по сравнению с "алгоритмами".

[Sonic86]

Рассмотрим задачу о переливании с 3-я конечными сосудами. Попробуем определить, какие состояния достижимы с помощью переливаний, а какие - нет.
Используем предложенную выше геометрическую интерпретацию. Если в $j$-м сосуде налито $x_j$ литров жидкости, то $(x_1;x_2;x_3)$ - целая точка в 3-хмерном пространстве. $x_1+x_2+x_3=V=\mathrm{const}, x_j\geqslant 0$ - это соотношения ограничивают треугольник в $\mathbb{R}^3$, далее, если $n_j$ - объем $j$-й банки, то получим еще ограничения $x_j\leqslant n_j$ - это 3 плоскости, при отсечении ими можем получить 3,4,5- или 6-иугольник. Фигуру и ее внутренности обозначим $F$, пересечение $F\cap \mathbb{Z}^3$ обозначим $G$. Допустимым переливаниям из банки в банку соответствуют отображения $\varphi$ точек из $G$ в $G$ по прямым, лежащим внутри $G$, параллельным какой-то координатной плоскости. Действие отображений незачем ограничивать только целыми точками $G$, лучше распространить его сразу на все $F$.
Задача о переливании примет вид: дана точка $M$ в $F$ и отображения $\varphi$. Определить, достижима ли или нет какая-то точка $H\in F$.
У $F$ есть собственно внутренность, границы и вершины. Ясно, что если исходная точка лежит на внутренности $F$, то любое действие переводит ее на границу $F$, причем не более чем 3-я способами. Далее рассматриваем только точки на границе.
Рассмотрим произвольную граничную точку из $F$, не являющуюся вершиной. Из нее можно сделать 4 варианта хода: 2 переводят точку в вершины, еще 2 - в другую граничную точку, не являющуюся вершиной. Первые 2 хода не рассматриваем. После того, как выбран один из 2-х вариантов хода, все последующие нетривиальные ходы (не отменяющие предыдущие) определяются единственным образом. Т.обр., у нас получается класс граничных точек, изоморфный $\mathbb{Z}$ по связности. Точки внутри класса достижимы. Достижимость точек, не явлющихся вершинами - отношение эквивалентности, так что граница $\partial F$ разбивается на классы. Если мы учтем еще и вершины, то мы получим, что граница фигуры $\partial F$ разбивается на 2 множества: $\partial F=F_1+F_2$, $F_1$ - множество вершин $\partial F$ и достижимых из них точек, $F_2=\partial F\setminus F_1$. Все точки $F_1$ достижимы из любой точки $F_2$, обратное неверно. $F_1$ представляет собой один класс эквивалентности по отношению достижимости, а $F_2$ может оказаться разбитым на множество классов.
Ясно, что все точки $F_1$ достижимы, остается рассмотреть $F_2$.
Будем рассматривать самый общий случай, когда $\partial F$ - 6-иугольник.
Покажем, что на длины сторон 6-иугольника можно наложить некоторые ограничения, не уменьшающие общности. Рассмотрим пары параллельных сторон 6-иугольника. Если в одной из пар стороны достаточно длинные, то их можно "уменьшить" следующим образом. Пусть $ABCDEF$ - 6-иугольник ($F$ здесь - это не та $F$, которая выше, а другая). Пусть $AB$ и $DE$ достаточно длинны. Тогда, если исходная точка $M\in AB$ например, то ее путь в границе $ABCDEF$ в результате отображений имеет вид: $M_0=M\to M_1\to M_2\to M_3\to...$, где $M_0, M_2, M_4,... \in AB$, а $M_1,M_3,...\in DE$. Если параллелограмм $M_0M_1M_3M_2$ "влазит" (существует) в $ABCDEF$, то его можно "вырезать" - построить новый 6-иугольник, получающийся склеиванием кусков $M_0ABCM_1$ и $M_2M_3DEF$, причем классы $F_2$ в новом 6-иугольнике являются ограничениями классов $F_2$ старого 6-иугольника (это несложно показать, я не буду это писать, а то длинно будет).
Будем применять подобную операцию "обрезания" исходного 6-иугольника до тех пор, пока она возможна. Полученный в результате 6-иугольник обозначим $F_X$. Заметим, что исходная задача на $F$ может быть сведена к рассмотрению аналогичной задачи в $F_X$ - вместо исходных точек в ней лишь следует брать их образа после преобразования "обрезания" $F$. В итоге, мы можем изначально считать $F$ обрезанным.
Далее, рассмотрим действие $\varphi$ на $F$. Это действие не является даже группоидом. Однако, действие можно свести к рассмотрению действия некоей группы на некотором множестве.
В качестве множества выберем 2 некоторых смежных ребра $F$ - $AB$ и $BC$ (точнее - все их точки из $F_2$) - "ломаная" $L$. В качестве действия на $M\in L$ выберем такую степень $k$ (возможно, зависящую от $M$), что $\varphi^k(M)$ снова лежит в $L$ (т.е. просто отображаем точку, пока она не вернется снова куда-то в $L$). Такое $k$ действительно существует для каждой точки (я, честно говоря, доказательство не писал явно, однако Вы можете убедиться в этом сами. Для этого нужно перебрать все возможные варианты сторон, в которые может попадать $M$ в результате действия $\varphi$ какое-то количество раз и увидеть, что какой-то образ $M$ опять попадает в $L$. (я специально выбрал в качестве $L$ две смежные стороны, одной стороны недостаточно. А вот для 5-иугольника можно выбрать одну сторону - у меня есть явный расчет) Далее, я замечу, что число шагов $k$ ограничено - в "обрезанном" 6-иугольнике верхняя его граница не зависит от параметров $V, n_j$, потому в $L$ попадает множество точек класса достижимости "конечного индекса").
Обозначим отображение, действующее в пределах $L$ буквой $\pi$. Действие $\varphi$ на пары точек в $\partial F$ локально сохраняет метрику, потому $\pi$ тоже ее сохраняет в $L$, потому, если $x$ - локальная координата в $L$, то $\pi(x)=A\pm x$. Значит $\pi$ - кусочно-линейная функция на $L$. Докажем, что число кусков в $L\cap G$, на которых $\pi$ линейна, ограничено абсолютной константой, не зависящей от параметров фигуры (т.е., что $\pi$ - перестановка). Для этого вернемся к рассмотрению $\varphi$ и вспомним, что стороны 6-иугольника - целые числа (а значит существует их НОД). Возьмем произвольную сторону $l\in L$ 6-иугольника. Рассмотрим ее образ $\varphi(l)$. Если он лежит внутри стороны 6-иугольника, то все нормально - отображаем дальше. Если он попал на несколько разных сторон 6-иугольника, то разобъем его на несколько отрезков так, чтобы отрезки отображались целиком внутрь своего ребра. Т.к. число сторон 6-иугольника ограниченно, то число таких отрезков тоже будет ограниченно. После нескольких разбиений отрезки из $l\in L$ снова попадут в $L$. Если $l$ и его образ пересекаются - разобъем их их пересечением. Получим, что каждая сторона $L$ была разбита на ограниченное число кусков, на которых $\pi$ действует линейно.
Таким образом, $\pi$ действует на $L$ кусочно-линейно, причем число кусков ограниченно абсолютной константой. Значит при действии $\psi$ на целую точку в $L\cap G$ мы получим орбиту ограниченной мощности. Поскольку 6-иугольник был "обрезан", то в "обрезанном" 6-иугольнике орбита каждой точки имеет ограниченную мощность.
Теперь уже понятно, что орбита вершин также имеет ограниченную мощность.
Отсюда следует, что если параметры 6-иугольника будут достаточно велики, то мы получим, что $F_2$ имеет $>1$ класса достижимости. В результате получаем, что задача может быть решена следующим образом - "обрезаем" нашу фигуру, после чего число достижимых состояний в результате переливаний станет равным $O(1)$ - все достижимые точки можно тупо вычислить. Если искомая точка находится среди достижимых, то задача имеет решение и его можно явно найти, иначе - нет.
Кроме того, для достаточно больших параметров $V, n_j$ существуют как 6-иугольники, в которых все точки достижимы, так и 6-иугольники, в которых некоторые точки недостижимы.

Надеюсь, что этот текст понятен
Могу пояснить детально.
Времени мало, но я могу еще подумать и написать более понятно.

[Утундрий]

Я упрощу: все достижимые состояния можно отыскать прямым перебором.

[Sonic86]

(нифига)

Утундрий в сообщении #888837 писал(а):

Я упрощу: все достижимые состояния можно отыскать прямым перебором.

Не, Вы написали, что число решений равно $O(V)$, а я - что число решений после "обрезания" фигуры равно $O(1)$.
Бе-бе-бе