И это и будут наши три цвета: ведь условие "a^{-1} b a = c" для транспозиций a,b,c из S_3 равносильно условию "либо все три совпадают, либо все три различны".

Вот, собственно, и всё — условие на правильность раскраски оказалось условием на гомоморфизм фундаментальной группы в S_3 (что соотношения выполняются). И число правильных раскрасок — это число вот таких гомоморфизмов.

Последний комментарий в виде ассоциации — шестая задача отсюда:
http://math.mosolymp.ru/upload/files/2017/khamovniki/10-1/2016.09.26_Vesa.pdf

(Не буду объяснять, почему, будет подсказка, но если что, рядом лежат и решения: via http://math.mosolymp.ru/2017_khamovniki_10_1 )

И на этом севшая батарея ноутбука намекает, что пора на сегодня прекратить дозволенные речи.

Вообще-то я собирался рассказывать про другое, но вчерашний доклад Микеле Триестино поменял мои планы:

Рассмотрим вот такую группу:

H_4=< a,b,c,d | aba^{-1}=b^2,
bcb^{-1}=c^2,
cdc^{-1}=d^2,
dad^{-1}=a^2 >

Собственно, индекс 4 подсказывает, что есть и группа H_n. У неё n образующих — a_1,...,a_n — и n соотношений:
a_i a_{i+1} a_i^{-1} = a_{i+1}^2.

Просто группы H_2 и H_3 оказываются тривиальны — а вот группа H_4 уже бесконечна. Что, впрочем, неочевидно, но пока мы в это поверим.

Так вот, с помощью этой группы Хигман в 1951-м построил первый пример бесконечной конечно-порождённой простой группы.

А именно, оказывается, что верно вот такое утверждение —

Теорема (Хигман, 1951): у группы H_n нет нетривиальных конечных факторов.

Забавным образом, эта теорема выводится из малой теоремы Ферма.

А именно: пусть у нас есть какой-то конечный фактор фактор одной из групп H_n. Он порождён образами b_i образующих a_i. Давайте докажем, что они все тривиальны.

Собственно, раз это фактор — на b_i выполнены те же соотношения, что и раньше на a_i, но в дополнение к ним и ещё какие-то.

Во-первых, если тривиален хотя бы один образ b_i, то тривиальны они все — потому что b_i сопрягает b_{i+1} с его квадратом; раз b_i=e, то сопряжение ничего не делает, и b_{i+1}=b_{i+1}^2, и тогда b_{i+1}=e.

Во-вторых, пусть теперь они все нетривиальны. Раз мы предположили, что фактор конечный, то это всё — элементы конечного порядка.
То есть у каждого b_i есть свой порядок m_i>1.

Мы знаем, что b_i сопрягает b_{i+1} с его квадратом, b_{i+1}^2.
Применив это m_i раз, получаем, что b_{i+1} совпадает со своей 2^{m_i}-й степенью:

То есть
b_{i+1}^{2^{m_i} - 1} = e,
откуда 2^{m_i} - 1 делится на m_{i+1}.