Теорема. Число правильных раскрасок — инвариант узла.

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

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

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

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

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

Например:

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

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

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

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

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

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

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

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

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

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

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