Математические байки

Во-вторых, условие "три одинаковых или три разных" встречается ещё в замечательной игре SET:

А это 3 в степени размерность пространства решений.

Оказывается, на это есть хороший ответ — но прежде ещё пара замечаний. Во-первых, мы между делом обнаружили, что число правильных трёхцветных раскрасок всегда будет степенью тройки. Потому что это число решений системы линейных (однородных) уравнений вида x_i+x_j+x_k=0 (где i,j и k — номера нитей, встречающихся в данном перекрёстке) над полем из трёх элементов.

Правда, всё равно остаётся ощущение чуда: почему именно при таких правилах получился инвариант?

А проверить движения R1 и R2 ещё быстрее.

И теперь уже мгновенно проверяется, что если три подходящих к R3-перестройке сверху (на рисунке выше) цвета это a, b и c (слева направо), то вниз они придут и в том, и в другом случае как -a+b+c, b и -(a+b).

Соответственно, мы можем работать в поле по модулю 3 — зная, что если два из подошедших к перекрёстку цветов это a и b, то третий это -(a+b).

(А третий цвет однозначно определяется двумя, так что переход в обратную сторону тоже мгновенный)

Действительно, 0+1+2=0 mod 3, 3x=0 mod 3.

И тут помогает вот какое наблюдение: обозначим наши цвета 0, 1 и 2. Три цвета удовлетворяют условию "все одинаковые или все разные" тогда или только тогда, когда их сумма равна 0 mod 3.

Ну или нужно сказать, что при данных цветах сверху, продолжая через картинку, мы и в том, и в другом случае получим всегда одни и те же цвета снизу — что уже более разумно, но всё ещё остаётся каким-то странным перебором.

Правда, проверять такое утверждение напрямую грустно: нужно для всех возможных наборов входящих снаружи цветов проверить, что либо одновременно внутрь продолжится, либо не продолжится, и это довольно много вариантов.

Например:

Как нас учат специалисты по комбинаторике, лучше всего равенство натуральных чисел доказывается биекцией. Так вот — между трёхцветными раскрасками есть биекция, сохраняющая раскраску вне перестраиваемой области (а легко видеть, что внутрь области перестройки раскраска всегда продолжается не более чем одним способом).

Соответственно, нужно доказать, что каждое такое движение не изменяет числа трёхцветных раскрасок.

(image credit: Wolfram Mathworld, http://mathworld.wolfram.com/ReidemeisterMoves.html )

Процесс деформации (гомотопии) одного узла в другой с точки зрения диаграмм разбивается на конечное число _движений Редемейстера_:

Как такое нужно доказывать? Как обычно: показывать, что в процессе перехода от одного узла к другому он не меняется.