Еще раз опишем задачу для наглядности:
Кладка это два параллельных ряда кирпичиков 3х видов (красок) с целыми длинами (
)
Кирпичи в рядах не могут соприкасаться цветами. Как только кирпичики в параллельных рядах сойдутся одним швом, то кладка заканчивается (т.е. внутри кладки невозможно появление общего шва для обоих рядов). Рассмотрим для примера кладку a=5, b=7, c=13
Как, видно возможно три симметричных решения:
Практически очевидно, что невозможно более трех решений, так как процесс закладывания кирпичей строго детерминирован цветом двух начальных кирпичей. Также очевидно, что для каждой тройки чисел найдется либо три симметричных решения, либо одно симметричное и одно несимметричное (опять таки, потому что процесс полностью определен двумя крайними кирпичами и он периодичен – длина периода это и есть длина кладки). Собственно задача в том, чтобы описать все тройки чисел, для которых три решения симметричны.
Далее будем рассматривать только нечетные тройки вида (
).
Основания для этого следующие: 1. четные тройки всегда можно разделить на два, не меняя решения. 2. тройки разной четности никогда не образуют три симметричных решения, ввиду невозможности симметричного наложения четного кирпичика на нечетный (в верхнем и нижнем рядах соответственно). 3. по статистике замечено, что не бывает
4. Всякое решение
не изменится если от
отнять
поэтому всегда можно ограничить
5. требование взаимной простоты не принципиально в описанной задаче и всегда может быть наложено на ответ при необходимости. 6. Метод нахождения общего решения для заданных троек работает наиболее просто, что не отменяет возможность его применения для произвольных троек.
Рассмотрим все возможные переходы на стыках.
На стыке левого и правого элементов- верхний(или нижний) элемент (далее - стыковой) никогда не должен равняться левому и правому (по условиям задачи).
Перечислим все возможные комбинации (левого и правого элементов) с учетом соответствующих стыковых элементов. Если стыковой элемент – с, тогда возможны только два перехода – aba и bab. Если стыковой элемент b, то переходы – ac, ca и cac. Если стыковой элемент – a, то переходы bc и cb. Это верно для всех троек
у которых
).
Назовем - левым смещением в стыке, разность между точкой (на координатном луче) отсчета начала перехода(левого элемента) и точкой начала стыкового элемента. Для нашего примера левое смещение первого кирпичика(стыкового) в первом ряду, в первом решении, равна нулю. Второй элемент верхнего ряда (розовый) не является стыковым, так как под ним нету стыка, поэтому пропускаем его. Наконец третий элемент первого ряда (красный) является стыковым. Относительно него левый элемент внизу – будет имеет “левое смещение в стыке(далее просто смещение)” равное |0-12|=12. (смещение всегда положительно либо ноль для начальных крайних элементов) На рисунке показано взаимнооднозначное соответствие между произвольным решением и направленным графом стыковых преобразований.
Функция перехода в стыке(относительно стыкового элемента x) – определяется как преобразование левого смещения стыкового элемента x(например верхнего) в левое смещение следующего стыкового элемента (уже нижнего или наоборот). Пусть некто каменщик начал укладывать кладку (два параллельных ряда), последовательно друг за другом. Состояние, в котором находится укладчик в данный момент можно однозначно описать двумя параметрами – стыковым элементом и левым смещением в стыке. Заметим что не каждый элемент стыковой, но это и не важно. Теперь построим граф состояний “почти” независящий от смещений. Возможные переходы (с)aba (с-стыковой элемент, aba – противолежащий ряд ряд) (с)bab, (b)ac, (b)ca, (b)cac, (a)bc, (a)cb – итого семь возможных состояний, и пять однозначных переходов между ними (независимо от смещений), два перехода зависят от смещений. Получаем направленный почти циклический граф переходов из 7 вершин.
Стартовать мы можем только из трех вершин (1,3,4) закончить путь(кладку) мы можем только в трех вершинах (1,4,5). Например, в вершине 2 не можем стартовать, потому что левый элемент c – длиннее, чем стыковой а. Если размножить дуги так, чтобы пронумеровать каждую возможным смещением, то получим детерминированный конечный автомат, хотя он и не нужен в дальнейшем. Примем здесь и далее
, тогда путь из вершины 7 в вершину 4 невозможен (это ограничение не выглядит принципиальным). Можно редуцировать этот граф в 6-вершинный (можно даже в 5-вершинный, поскольку путь из 1 в 3 однозначен), учитывая, что 5-ая вершина не может быть начальной, получим:
Опишем теперь, как преобразуется смещение при выходе из вершин.
Вершина 1[(с)aba]
если
=> конец кладки (вершина E)
Вершина 2[(a)cb]
Вершина 3[(b)ac]
Вершина 4[(с)bb]
если
=> конец кладки (вершина E)
Вершина 5[xxx]
Если
то
Если
то
Если
=> [(b)ca]=> конец кладки (вершина E)
Если
=> [(b)cc]=> [(c)bb]=> конец кладки (вершина E)
Вершина 6[(a)bc]
При каждой вершине только один переход (стрелка в графе) в следующую за ней. При вершине 6 переход в вершину 1.
Теперь распишем циклический путь в графе(без учета путей в E). Стартуем из вершины 1
1-2
2-3
3-4
4-5
5-6 // При условии, что
6-7
после прохождения первого цикла x при вершине 1 увеличится на
, после
шагов увеличится на
[если конечно не завершится путь и если условие на шаге 5-6 сохраняется]
Второй вариант циклического пути. Стартуем из вершины 1.
1-2
2-3
3-4
4-5
5-6 // При условии, что
6-7
после прохождения первого цикла
при вершине 1 увеличится на
, после
шагов увеличится(а точнее уменьшится) на
[если конечно не завершится путь и если условие на шаге 5-6 сохраняется].
После
циклов по первому варианту и
циклов по второму варианту (неважно в какой последовательности) получим, что
изменится на
.
Итак, для образования трех симметричных решений тройкой чисел
необходимо, чтобы, стартовав из первой вершины путь закончился в ней же, а не где-нибудь еще. Начальный
(смещение) всегда равен нулю.
Проверим условие окончания пути в вершине 4:
в ней равно
. Условие завершения - если
. Подставляем и смотрим равно ли:
что невозможно ни при каких обстоятельствах, так как
неотрицательное число. Это означает, что условие завершение в вершине 4 – фиктивное, и его можно было бы исключить с самого начала для любых вариантов.
Проверим условие1 окончания пути в вершине 5:
в ней равно
. Условие1 завершения – если
. Подставляем и смотрим равно ли:
очевидно, что равенство невозможно ни при каких
и
, поскольку части разной четности.
Проверим условие2 завершения пути в вершине 5:
в ней равно
. Условие2 завершения – если
. Подставляем и смотрим при каких
и
выполняется равенство:
Итак, при
и
, удовлетворяющих уравнению
, происходит выход и симметричное решение невозможно. Остается найти при каких
выход по условию при вершине1 возможен и произойдет “раньше” (поясняется ниже).
Проверим условие завершения пути в вершине 1:
в ней равно
. Условие завершения – если
. Подставляем и смотрим при каких
и
выполняется равенство:
поскольку мы с самого начала рассматриваем только тройки в которых
, то условие трансформируется
. Оно выполняется тогда и только тогда, когда
делится на
, что эквивалентно:
, т.е. наибольший общий делитель двух чисел равен 2.
Теперь возникает вопрос – всегда ли уравнение
будет иметь меньшее по
положительное решение, чем уравнение
, при условии
. (Во втором уравнении мы записали вместо переменной
переменную
, тогда требование: «меньшее либо равное” преобразуется в “строго меньшее”)
Чтобы сравнивать конкретные решения данных уравнений, необходимо прояснить один важный вопрос. Очевидно, что каждому завершенному пути из первой вершины- соответствует некоторое решение уравнения (первого или второго), однако неясно соответствует ли каждое решение уравнения некоторому завершенному пути. Поскольку
при первой вершине четное, и не может повторяться от цикла к циклу, то оно может принимать всего
– различных значений(от 0 до
) и соответственно всегда:
для обоих уравнений. В этом случае достигается взаимнооднозначное соответствие между решениями уравнений и завершенными путями, поскольку тогда уравнения имеют только по одному решению (этот параграф требует большей проработки).
Тогда единственным решением второго уравнения, является пара:
, поэтому если решение первого уравнения существует, то оно будет меньше по
, ведь
ограничивается сверху для обоих уравнений числом
.
Итак, путь, стартующий из первой вершины, завершится в ней же при условии
. Что можно сказать, относительно пути, стартующего из четвертой вершины? Используя похожие соображения, что и для завершения пути из первой вершины в пятой по условию1, можно сделать вывод, что завершение пути из 4 вершины в 5-ой вершине, по условию 1 – невозможно (несовпадение четности левой и правой части в условии). Также, невозможно его завершение в первой вершине, т.к. там уже завершается другой путь. Завершение в четвертой вершине – невозможно в принципе. Остается только завершение в 5-ой вершине по условию 2. Значит, данный путь всегда симметричен (при условии симметричности пути из 1-ой вершины), а значит все три решения -симметричны.
Итак, необходимым и достаточным условием на произвольные нечетные тройки
(где
и
) является
, в частности:
. Вполне возможно, что общее решение для всех троек определяется системой похожих соотношений.
, 
. Тогда алгоритм построения кладок получается следующий:
, если ряды начинаются с кирпичиков c,a
, если ряды начинаются с кирпичиков a,b
, если ряды начинаются с кирпичиков b,c
, то закончить алгоритм, конечные кирпичи в рядах: b,a
, то закончить алгоритм, конечные кирпичи в рядах: c,a
, то закончить алгоритм, конечные кирпичи в рядах: c,b
.
не просто. Для симметричных кладок при 
существует не рекуррентная формула?