Pilot Brothers Puzzle

О чем речь?

В седьмом эпизоде игры Братья Пилоты необходимо решить задачу с переключателями. В этой задаче дана матрица 4x4 из переключателей, каждый из которых может быть либо в горизонтальном, либо в вертикальном положении. Переключатели можно поворачивать, но при этом одновременно поворачиваются все переключатели на той же строке и в том же ряду матрицы. Изначально переключатели расставлены произвольно. Цель --- перевести все переключатели в горизонтальное положение.

Вращая переключатели наобум, понимаешь, что времени таким образом можно потратить сколько угодно, но если я не ошибаюсь, официальная подсказка на http://www.1c.ru рекомендует делать именно это.

Желающие могут потренироваться на апплете:

Однако, как ни удивительно, есть очень простой алгоритм, который позволяет решать эту задачу не более чем за 16 поворотов переключателей!

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

1. подсчитать число переключателей в вертикальном положении на той же строке, что и данный, учитывая, если надо его самого
2. прибавить к нему число переключателей в вертикальном положении в том же столбце, что и данный, учитывая, если надо его самого
3. прибавить единицу, если переключатель сам в вертикальном положении
4. если получилось нечетное число (намек: 1, 3, 5 <g>), повернуть переключатель, иначе не делать ничего.

Что, однако, еще более удивительно, по-крайней мере мере для автора, это то, что этот алгоритм был получен чисто аналитическим путем, без какого-либо экспериментирования (не считая 10 минут безуспешного и бессистемного щелкания мышкой). Для интересующихся ниже приведено доказательство.

Д о к а з а т е л ь с т в о

Для начала, рассмотрим несколько обобщенную форму задачи: пусть дана матрица размером m x n (m строк, n столбцов), каждый элемент которой --- переключатель a_ij, где 1<=i<= m, 1<=j<=n, который может находиться в одном из r_ij положений (r_ij>1), либо переключатель с бесконечным (счетным) числом возможных положений. В последнем случае положим r_ij=0. Таким образом, получается матрица R = (r_ij).

Чтобы получить исходную задачу надо положить n=m=4, r_ij=2.

Назовем положением произвольную конфигурацию переключетелей на доске. Каждая конфигурация, это матрица (x_ij) m x n, такая что элемент x_ij принадлежит абелевой группе Z/r_ijZ, где Z --- абелева группа целых чисел, по сложению, а r_ijZ --- ее подгруппа, чисел кратных r_ij. Если r_ij = 0, то r_ijZ = 0 и, как и требуется Z/r_ijZ=Z/0Z=Z/0=Z. Множество всевозможных положений обозначим X (на самом деле X это функция X(n,m,R)).

В качестве примечания, отметим, что множество X можно само снабдить структурой абелевой группы, которая при этом естественным образом оказывается разложенной в свободную сумму _i,j Z/r_ijZ.

Назовем попыткой, произвольную последовательность поворотов перключателей на доске. Если a и b попытки, то можно выполнить сначала попытку a, а затем b. Получившаяся попытка будет обозначаться ab. Очевидно, что a(bc)=(ab)c, т.е. попытки образуют полугруппу (т.е., множество со вседу определенной ассоциативной операцией). Формально добавим пустую попытку (т.е. попытку не производящую никаких изменений в конфигурации) и обозначим ее 1. Тогда для любой попытки a, имеем 1a=a1=a, таким образом мы получаем моноид (т.е., полугруппу с единицей), обозначим его G.

Назовем элементарной попыткой b_ij поворот переключателя a_ij на одну позицию (что приводит к соответствующим поворотам в строке и столбце). По определению, G, порождается элементарными попытками, т.е., каждый элемент g может быть представлен как произведение g=b_(i1)(j1)...b_(ik)(jk). Можно легко проверить, что любые две элементарные попытки коммутируют, т.е. b_(i1)(j1)b_(i2)(j2)=b_(i2)(j2)b_(i1)(j1), поэтому и любые попытки коммутируют: ab=ba, таким образом, G --- коммутативный моноид. Произведение в нем будем записывать, как сумму, а единицу, как 0: a+b=b+a, a+0=0+a=a.

Примечание: исходную задачу можно обобщить несколькими разными способами. Именно, как только у нас появляются переключатели со счетным количеством положений, нужно различать повороты по и против часовой стрелки. Действительно, если все r_ij отличны от нуля, рассмотрим какое-нибудь их общее кратное r (например, наименьшее общее кратное). Тогда, как легко убедиться, повернув произвольный переключатель r раз мы вернемся в исходное положение, т.е. rb_ij=0, а значит, и для всякой попытки g, rg=0 (все элементы моноида имеют конечный порядок). Более того, пусть r' --- общее кратное всех чисел r_ij-1 (каждое из которых больше нуля), тогда повернув a_ij r' раз мы получим, что все переключатели на той же строке и в том же столбце окажутся повернутыми один раз в ,,противоположном направлении``. Если после этого повернуть a_ij еще один раз, то мы вернемся в исходное положение, т.е. r'b_ij+b_ij=0. Таким образом, у каждого b_ij есть обратный b_ij^-1=r'b_ij. Но, следовательно, есть обратный и у каждого g из G, так все они предствляются как сумма b_ij. Следовательно G --- абелева группа.

Если же есть r_ij=0 (т.е., есть переключатель с бесконечным количеством положений), то для того чтобы сделать G группой, необходимо добавить в G элементарные попытки, поворачивающие переключатели в противоположном направлении и все их линейные комбинации.

Итак, мы имеем коммутативный моноид G и множество X. G порождается элементами b_ij, т.е., всякий g из G может быть записан в виде g=_i,j g_ijb_ij для некоторой матрицы целых коэффициентов (g_ij). Более того, определено действие моноида G на множестве X, а именно, для положения x и попытки g определим положение A(g,x), как положение, в котором оказывается доска, после применения попытки g в положении x. Таким образом задано отображение X A:G x X -> X. Ему сооветствует отображение A':G -> End(X, X), где End(X,X) --- моноид отображений множества X в себя. Отображение A является действием моноида на множестве, т.е., A' является гомоморфизмом моноидов. Действительно, A(0,x)=x и A(g₁g₂,x)=A(g₂,A(g₁,x)).

Как уже было сказано, X можно отождествить с абелевой группой матриц по сложению. Существует замечательный гоморфизм коммутативных моноидов f:G->X, такой что A(g,x)=f(g)+x. Этот гомоморфизм переводит попытку b_ij в матрицу (e_ij), такую что e_pq=1 если p=j или q=j и равно нулю в противном случае (т.е., в (e_ij) стоят единицы в i-й строке и j-м столбце):

На весь моноид G отображение распространяется по линейности, т.е. если g=_i,j g_ijb_ij, то f(g)=_i,j g_ij(mod r_ij)e_ij. Это распространение корректно, действительно, пусть g=_i,j g_ijb_ij и g=_i,j g'_ijb_ij два разных разложения одной и той же попытки, то _i,j g_ijb_ij - _i,j g'_ijb_ij=0, а это возможно если и только для всех i, j g_ij=g'_ij (mod r_ij).

Если f окажется эпиморфизмом (сюръективным отображением), то задача всегда имеет решение. Дествительно, пусть x₀ начальное положение, а x₁ --- конечное. Например, в исходной задаче x₀ это некоторая заданная конфигурация, а x₁ состоит из одних единиц. Так как f --- эпиморфизм, то существует попытка g такая, что f(g)=x₁-x₀. Тогда A(g,x₀)=f(g)+x₀=x₁-x₀+x₀=x₁, т.е., g переводит x₀ в x₁.

Если при этом f еще и мономорфизм (инъективное отображение), то решение единственно. Пусть f(g)=x₁-x₀. Так как f мономорфизм, то существует отображение h:X->G, такое что h(f(g))=g. В частности, g=h(f(g))=h(x₁-x₀).

Более того, в случае исходной задачи (n=m=4, r_ij=2), f является даже изоморфизмом и обратный к нему изоморфизм h, позволяющий вычислять решения, имеет достаточно простой вид.

Итак, надо решить задачу f(g)=s, где s=(s_ij) --- положение, а g=_i,j g_ijb_ij --- попытка. Подставляя определение f получаем систему уравнений _i,j g_ije_ij = s_ij (mod r_ij). Всякая матрица e_ij может быть представлена в виде e_ij = _pb_ip + _qb_qj - b_ij. Поставляя это в предыдущее уравнение, и проводя выкладки (которые мы опускаем, так как понять их в HTML все равно не возможно) получаем: _pg_ip + _qg_qj - g_ij = s_ij (mod r_ij).

Упражнение: определите как выглядит матрица левых частей этой системы уравнений.

Рассмотрим матрицу U, такую что U_ij=1. Тогда, очевидно, _pg_ip =  _pU_pjg_ip =  (gU)_ij --- элемент матрицы произведения. Аналогично _qg_qj =  _qU_iqg_qj =  (U'g)_ij, где U' матрица такой же структуры как и U, но другого размера. Таким образом, наша система сводится к матричному уравнению: gU + U'g - g = s (mod R).

Переписав это уравнение в виде g = gU + U'g - s (mod R), можно попытаться решить его итерационным способом. Именно, если у нас уже есть n-е приближение gⁿ, то подставим его в правую часть уравнения, и выберем левую часть, как (n+1)-е приближение: gⁿ⁺¹ = gⁿU + U'gⁿ - s (mod R). Начиная с нулевого приближения равного нулю, получаем последовательность приближений: 0, -s, -sU - 'Us - s, -U'²s - 2U'sU - U's - sU² - sU - s и т.д.

Очевидно, что U²=m²U и U'²=n²U'.

Рассмотрим частный случай, когда n и m --- четные числа и все r_ij=2. Тогда U²=n²U=0=U'²=m²U' (mod 2) и 2U'sU=0 (mod 2). Тем самым, третье приближение равно второму, т.е. второе приближение обращает уравнение в тождество, т.е. является решением! Итак в этом случае, и, в частности, в исходной задаче решение имеет вид: g = -sU - U's - s (mod 2).

Вспомним опять, что (sU)_ij это сумма элементов i-й строки матрицы s, а (U's)_ij сумма элементов j-го столбца и получим алгоритм описанный в самом начале!

Я хотел бы поблагодарить лекторов и семинаристов по дискретному анализу физтеха, которые считали, что общая алгебра (в частности, теория групп и модулей и категорий) достаточно проста, чтобы каждый мог изучить ее самостоятельно, перед тем как заниматься серьезными вещами, такими как криптография и теория сложности.

[ Sign my GuestBook ] - [ Read my GuestBook ] - [ Home page ]