Волшебные цветные рыбки

[DVL]

В задаче "Волшебные цветные рыбки" (Д.Златопольский, "Наука и жизнь", 2026, №7, с.89) нетрудно найти необходимое и достаточное условие возможности перехода от любого распределения рыбок по цвету к другим и алгоритм кратчайшего перехода.
Для тех, кому недоступен этот номер журнала, поясню, о чем идет речь в этой задаче. "В аквариуме плавают несколько красных, синих и зеленых рыбок. Если друг друга касаются две рыбки одного цвета, то ничего не происходит, а если разного цвета, то они окрашиваются в третий цвет." Далее в задаче требуется осуществить конкретные переходы от одних распределений рыбок по цвету к другим за минимальное количество касаний.

[CosPi]

В дополнение к стартовому посту DVL — критерий разрешимости, явная формула минимального числа касаний и кратчайший путь без перебора. Единственная тонкость — одноцветные состояния (п. 4).

1. Состояние — тройка $(r,b,g)$ неотрицательных чисел, $r+b+g=n$. Касание рыбок разных цветов прибавляет один из векторов $(-1,-1,2)$, $(-1,2,-1)$, $(2,-1,-1)$ в координатах $(r,b,g)$; касание рыбок одного цвета состояние не меняет и не рассматривается.

2. Пусть из $A$ за $s$ касаний получено $B$, $t_r,t_b,t_g$ — числа касаний, рождающих соответствующий цвет, $t_r+t_b+t_g=s$. Цвет при касании либо теряет одну рыбку, либо получает две, поэтому для любого цвета $X$

$$B_X-A_X+s=3t_X.$$

Иначе говоря, по модулю 3 каждое касание уменьшает каждый цвет на единицу: $2\equiv-1\pmod 3$.

3. Отсюда:
— инвариант: разности $r-b$, $r-g$, $b-g$ неизменны по модулю 3, причём при фиксированном $n$ одна из них определяет остальные, например $r-g\equiv-(r-b)-n\pmod 3$;
— оценка снизу: из $t_X\ge0$

$$s\ge d:=\max\{A_r-B_r,\;A_b-B_b,\;A_g-B_g\};$$

— длины путей: $s\equiv A_r-B_r\pmod 3$ (все три разности $A_X-B_X$ сравнимы между собой), поэтому длины — только $d, d+3, d+6,\ldots$; три касания разных типов вместе состояние не меняют — сумма векторов нулевая.

4. В одноцветном состоянии касание невозможно: из него достижимо только оно само. При $n\equiv0\pmod 3$ все три одноцветных состояния лежат в одном классе инварианта и друг в друга не переходят — это единственный случай, когда инварианты совпадают, а перехода нет.

5. Теорема. Для $A\ne B$ переход $A\to B$ возможен тогда и только тогда, когда (i) $n_A=n_B$; (ii) $A_r-A_b\equiv B_r-B_b\pmod 3$; (iii) в $A$ есть рыбки хотя бы двух цветов. Минимум касаний равен $d=\max_X(A_X-B_X)$, и мультимножество касаний всякого кратчайшего пути одно и то же: рождающих цвет $X$ ровно $\frac{d-(A_X-B_X)}{3}$. Цвет с максимальной разностью не рождается вовсе; если максимум на двух цветах — все касания одного типа.

Необходимость: (i) и (ii) — инвариант, (iii) — невозможность касания.

Достаточность. Пусть максимум достигается на зелёном. Возьмём $p^*=\frac{d-(A_b-B_b)}{3}$ касаний $P$ «(к,з)→с» с вектором $(-1,2,-1)$ и $q^*=\frac{d-(A_r-B_r)}{3}$ касаний $Q$ «(с,з)→к» с вектором $(2,-1,-1)$: целочисленность даёт инвариант, неотрицательность — определение $d$, $p^*+q^*=d$, и итог — ровно $B$. Тупик на пути невозможен: после $p\le p^*$ шагов $P$ и $q\le q^*$ шагов $Q$, пока что-то осталось,
— зелёных $g=B_g+(p^*-p)+(q^*-q)\ge1$;
— если остались только $P$, то $q=q^*$ и $r=B_r+p^*-p\ge B_r+1\ge1$;
— если только $Q$, то $p=p^*$ и $b=B_b+q^*-q\ge B_b+1\ge1$;
— если остались оба типа, а оба шага недопустимы, то $r=b=0$: из $r=A_r+2q-p=0$ следует $p\ge2q$, из $b=A_b+2p-q=0$ — $q\ge2p$, откуда $p\ge2q\ge4p$, то есть $p=q=0$ и $A_r=A_b=0$ — одноцветный старт, исключённый условием (iii).

6. Алгоритм: проверить (i)–(iii); ответ — $d$; путь — не касаться пары, порождающей цвет с максимальной разностью $A_X-B_X$, остальные касания выполнять в любом допустимом порядке.

Геометрически: состояния при фиксированном $n$ — узлы треугольной решётки, касания — шаги по трём из шести направлений, обратный шаг стоит два. Отсюда асимметрия расстояний: $d(A,B)+d(B,A)=\max_X(A_X-B_X)-\min_X(A_X-B_X)$.

7. Пример: $n=6$, $A=(1,1,4)$, класс инварианта содержит все одноцветные состояния:
— $A\to(0,0,6)$: одно касание (к+с → две з);
— $A\to(6,0,0)$: четыре: $(1,1,4)\to(3,0,3)\to(2,2,2)\to(4,1,1)\to(6,0,0)$;
— $(3,0,2)\to(1,4,0)$: два касания, обратно — четыре.

8. Упражнение: доказать, что нетривиальный возврат в исходное состояние возможен из любого состояния, кроме одноцветных и $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$.

[ozheredov]

CosPi в сообщении #1734456 писал(а):

Касание рыбок разных цветов прибавляет один из векторов $(-1,-1,2)$, $(-1,2,-1)$, $(2,-1,-1)$ в координатах $(r,b,g)$

Неочевидно. Цвет рабки кодируется одной единицей и двумя нулями, поэтому надо добавлять вектор с одной нулевой координатой и двумя единичными, в сумме равными нулю. Чего я не понимаю?

[CosPi]

ozheredov, про одну рыбку всё так и есть: её перекраска — вектор с одной нулевой координатой, скажем красная$\to$зелёная даёт $(-1,0,+1)$. Но векторы из п. 1 добавляются к тройке $(r,b,g)$ — численностям по цветам, то есть к сумме всех одно-рыбковых кодов. Касание перекрашивает сразу двух, обеих в третий цвет, поэтому дельта — сумма двух таких векторов: $(-1,0,+1)+(0,-1,+1)=(-1,-1,+2)$. Одиночной перекраски, дающей $(0,+1,-1)$, правилом не предусмотрено.