Часть II

Новая физика, необходимая для понимания разума. В поисках невычислительной физики разума


...

Приложение B: Нераскрашиваемость додекаэдра

Напомним условие задачи, поставленной в §5.3. Предлагается показать, что невозможно раскрасить все вершины додекаэдра в БЕЛЫЙ и ЧЕРНЫЙ цвета, соблюдая следующие условия: две «следующие соседние» вершины не могут обе быть БЕЛЫМИ, а шесть вершин, соседних с двумя противоположными (антиподальными) вершинами, не могут быть все ЧЕРНЫМИ. При исключении возможных вариантов раскраски чрезвычайно полезной оказывается симметричность додекаэдра.

Обозначим вершины, как указано на рис. 5.29. Вершины A, B, C, D и E образуют ближайшую к нам пятиугольную грань додекаэдра; дальше, в том же порядке, следуют соседние с ними вершины F, G, H, I и J. Как и в §5.18, соответствующие антиподальные вершины обозначены через A*, …, J*. Для начала отметим, что, согласно второму свойству условия, среди вершин додекаэдра хотя бы одна должна быть БЕЛОЙ — пусть это будет A.

Предположим теперь, что среди непосредственных соседей БЕЛОЙ вершины A имеется еще одна БЕЛАЯ вершина — скажем, B (см. рис. 5.29). Тогда все десять вершин, окружающие эту пару, — C, D, E, J, H*, F, I*, G, J* и H — должны быть ЧЕРНЫМИ, так как каждая из них является следующей соседней по отношению либо к A, либо к B. Далее, возьмем шесть вершин, соседних с вершинами из антиподальной пары H, H*. В этой шестерке должна быть хотя бы одна БЕЛАЯ вершина, значит, БЕЛОЙ будет либо F*, либо C* (или обе сразу). Проделав ту же процедуру с парой J, J*, приходим к выводу, что здесь БЕЛОЙ должна быть либо вершина G*, либо E* (или, опять же, обе сразу). Но это невозможно! И G*, и E* являются следующими соседними по отношению как к F*, так и к С*. Следовательно, вариант, когда у БЕЛОЙ вершины А имеется БЕЛЫЙ же непосредственный сосед, исключается — в самом деле, ввиду симметричности додекаэдра, невозможной оказывается любая пара соседних БЕЛЫХ вершин.

Таким образом, вершина A должна быть окружена исключительно ЧЕРНЫМИ вершинами B, C, D, E, J, H*, F, I* и G, поскольку каждая из этих вершин является по отношению к A либо соседней, либо следующей соседней. Обратим наше внимание на шесть вершин, соседних с вершинами из антиподальной пары A, A*. Очевидно, что одна из вершин B*, E* или F* должна быть БЕЛОЙ, причем, в силу симметричности додекаэдра, неважно, какая именно, — пусть будет F*. Отметим, что вершины E* и G* являются следующими соседними по отношению к F*, значит, они обе должны быть ЧЕРНЫМИ; ЧЕРНОЙ должна быть и вершина H, поскольку она соседствует с F*, а мы только что исключили возможность существования соседних БЕЛЫХ вершин. Однако так раскрашивать вершины нельзя, потому что при этом все соседи антиподальных вершин J, J* оказываются ЧЕРНЫМИ. Вот, собственно, и все доказательство — в классическом мире магические додекаэдры невозможны!