Милая задачка, доступная первокурснику (или школьнику, знающему, что такое векторное произведение).
Пусть i,j,k — ортонормированный базис трехмерного евклидова пространства. Как известно, трехмерные векторы можно векторно перемножать. Также широко известно, что операция векторного произведения не является ассоциативной. Например, [[i, j], j] = -i, но [i, [j, j]] = 0. Поэтому в произведении N векторов важно, как расставлены скобочки — это влияет на результат умножения.
Пусть A и B — две произвольные расстановки скобочек. Доказать, что существует набор векторов v1,...,vN, таких что их произведения, посчитанные с помощью расстановок A и B совпадают (и не равны 0), причем каждый из векторов vs является одним из базисных: i, j или k.
(Замечание: без последних двух условий задача была бы тривиальной — достаточно было бы взять нулевые векторы. Кто заранее знает решение этой задачи — просьба не палить).
Схема решения. Более подробное можно найти в Kauffman "Map coloring and vector cross product", J. of combinatorial th., Ser B, V28, N2 (1990).
ОтветитьУдалитьЛемма 1. Грани всякого плоского графа можно покрасить правильным образом в 4 цвета.
■Это теорема о 4х красках. Сейчас вроде бы общепризнано, что она доказана. ■
Лемма 2. Ребра двусвязного тривалентного плоского графа можно покрасить в три цвета так, чтобы ребра, инцидентные одной вершине имели разные цвета.
■Покрасим грани имеющегося графа в 4 цвета по предыдущей лемме, причем будем отождествлять цвета с элементами 4-группы Клейна Z/2Z+Z/2Z. Рассмотрим произвольное ребро е. Слева и справа от него находятся разные области (т.к. граф двусвязен), покрашенные в различные цвета Ы и Ё. Покрасим ребро цветом Ы+Ё.
Таким образом все ребра будут покрашены ненулевыми элементами 4-группы, т.е. тремя красками. То, что ребра выходящие из каждой вершины покрашены в три разных цвета проверяется непосредственно. ■
Итог: ребра каждого двусвязного тривалентного графа можно покрасить правильным образом в три цвета i, j, k.
Вернемся к исходной задаче.
■Вспомним, что каждая расстановка скобок (ассоциатор, по-научному) в неассоциативном произведении N элементов соответствует бинарному корневому дереву с N листьями.
Пример:
............... /\
((ab)c) ---> /\.\
..............a b c
Принцип, я думаю, понятен. У нас же заданы два ассоциатора A и B на N элементах. Нарисуем соответствующие им деревья на одном рисунке (на общих листьях), только одно пустим корнем вверх (как в примере), а другое -- корнем вниз (как учат в биологии). Примерно так:
............... /\
((ab)c) ---> /\.\
..............a b c
(a(bc)) ---> \.\/
................\/
И, наконец, соединим корни этих двух деревьев дужкой, не пересекающей уже нарисованные ребра.
Получился граф. Очевидно, плоский. Очевидно, двусвязный. Очевидно, тривалентный (вершины степени два, которые получаются из листьев, нужно "сгладить"). Покрасим его ребра в три цвета i,j,k по лемме 2.
ОтветитьУдалитьКаждое промежуточное умножение в каждом из ассоциаторов в графической переформулировке означает просто вершину степени три. В эту вершину "входят" два аргумента, а выходит их произведение. Если бы векторное произведение задавалось правилами ij=ji=k, ik=ki=j, jk=kj=i, то наша раскраска ребер графа задала бы правильную последовательность умножений: в каждую вершину входят два различных цвета, а в итоге получается третий цвет. Тогда наша задачка бы окончательно решилась: на корне первого дерева висит тот же вектор, что и на корне второго, так как они оба совпадают с цветом внешней дужки.
Однако же правила умножения векторов у нас другие: ij = -ji = k, -ik=ki=j, jk=-kj=i. Поэтому реально нам удалось доказать следующий факт: существует такой набор векторов, что их произведение, посчитанное по первому ассоциатору совпадает с их произведением, посчитанным по второму ассоциатору, с точностью до знака. ■
Оставшаяся часть доказательства занимает бОльшую часть объема вышеупомянутой статьи. Там используется какая-то хитрая конструкция из теории плоских графов, ссылающаяся на другие работы, etc... Пришлось придумать более простое док-во.
Лемма 3. Пусть v_1,...,v_N -- набор векторов, каждый из которых является одним из базисных i,j,k; а A и B -- два ассоциатора. Пусть произведения векторов, посчитанные по первому и по второму ассоциатору ненулевые. Тогда произведения равны.
■ Вспомним о кватернионах. Кватернионы H --- это алгебра над R, с линейными образующими 1,i,j,k и мультипликативными соотношениями ij = -ji = k, -ik=ki=j, jk=-kj=i, i^2=j^2=k^2 = -1. Образующие i,j,k называются базисными мнимыми единицами. Заметим, что умножение базисных мнимых единиц почти совпадает с векторным умножением векторов в R^3. За тем лишь исключением, что 0 = [i, i] =\= i^2 = -1. Но посмотрим на наши векторные произведения. В промежуточных операциях нигде не появляется [+/-i, +/-i], [+/-j, +/-j], [+/-j, +/-j], в противном случае всё произведение занулилось бы, а это противоречит условию. Значит на промежуточных этапах каждый раз вычисляется произведение разных символов. А значит, это же произведение можно подсчитать как умножение мнимых единиц в кватернионах -- в итоге получится тот же символ с тем же знаком. Получили
A(v_1,...,v_N)_[] = A(v_1,...,v_N)_H
B(v_1,...,v_N)_[] = B(v_1,...,v_N)_H
Но:
A(v_1,...,v_N)_H = B(v_1,...,v_N)_H
поскольку кватернионы являются ассоциативной алгеброй, а значит неважно как ставить скобки.