Теорема Царя пауков

Введение. Из всех знаменитых математических проблем самой простой для понимания считается проблема четырёх красок: утверждется, что любую карту (на плоскости) можно раскрасить в 4 краски.Для тех,кто не знает, напомню что 1.Страной считается какая-то связная фигура, то есть страны не имеют анклавов. 2 Две граничащие страны раскраиватся в различные цвета. Эта проблема заслуживает отдельного разговора, мы же пока перейдем от карт к графам: внутри каждой страны возьмем точку, если две страны
имеют общую границу, то две точки, взятые в этих странах, соединим линией, которая идет по территории этих стран и пересекает их общую границу.  Точки, правда, нельзя раскрашивать(точку не нарисуешь), но можно изобразить их достатаочно маленькими кружками, не имеющими пересечений между собой и с границами.Теперь соединенные линиями кружки красятся в разный цвет аналогично странам.
    рис.1 Переход от карт к графам
В завершение введем понятие цветных линий : пусть каждой линии соответствует свой цвет, причем пересекаться могут только разноцветные линии.(в случае одного цвета линий, который соответсвует обычной карте, соединительные линии тоже не пересекаются.) .Страны (кружочки), соединенные  между собой линией любого цвета, должны раскрашиваться в разные цвета(т.к. граничат).  С введением понятия цветных линий (многоплоскостного графа) возникают следующие проблемы
(1.)Любой ли граф, где можно проводить линии N цветов, можно покрасить пользуясь не более чем 4N цветами и (2)есть граф, для раскраски которого не обходимо ровно 4N красок?(аналог проблемы 4х красок, только гораздо сложнее, т.к. проблема 4х красок –лишь ее частный случай для N=1).Эту теорему я назову Теоремой царя пауков (по праву первооткрывателя).

Доказательство теоремы царя пауков я начну с пункта(2) , т.к. докакзательство пункта (1) даже для частного случая N=1 (было доказно в 1970е) занимает слишком монго страниц и компьютерных вычислений, а доказательство для произвольного N у меня получилось еще длиннее(более 1000 страниц).

 
            Рис.2 Пример построения по алгоритму для N=2
.Общая конструкция графа, для раскраски которого необходимо 4N красок.
Возьмем 4N точки (кружка) и разделим их на 2 группы (пополам). Рассмотрим одну из групп. Занумерум точки (1,2,....2N).
Идея построения следующая: пусть объединение линий каждого цвета в группе 2N  представляет собой отрезок (если спрямить), причем на каждый (из N) отрезок(кривую, если не спрямлять, здесь и далее имеется ввиду несамопересекающаяся кривая) нанизываются все 2N точки. Бесполезные (дублирующие) связи не проводятся (*).
При таком соединении каждая точка группы соседствует с остальными. Действительно- на точку не может приходиться более 2N-1 линии –соединена со всеми остальными, а всего по алгоритму проводится N*(2N-1) линий. Каждая линия соединяет 2 точки, бесполезныых не проводим, если есть 2 несоединенные точки , то всего линий не более ;*((2N-1)*(2N-2)+2(2N-2))= (N-1)(2N+1)<N(2N-1). (Первое слагаемое – через 2N-2 точки проведено 2N-1 линий (полное соединение), второе слагаемое- 2 несоединенные между собой точки. Значит 2х несоединенных точек нет. Доказано.
Далее, во второй группе 2N делаем также. Теперь заметим, что из каждой точки 2й группы можно провести линии любого цвета к 1й(т.к. относительно любого цвета, объединение линий этого цвета-отрезок).К каждому оттрезку можно приклеится с двух сторон (см. Рис.2, черный цвет).Осталось провести пучки линий цвета Ц к одной из стороно отрезка цвета Ц из 1й группы. Сторон отрезка-2,цветов линий –N, точек в группе как раз 2N. Поэтом можно провести по паре пучков каждого цыета к кривой того же цвета из 1й группы(один пучок- из одной точки к одной стороне отрезка). Тогда важдая из 4N точек соединена с остальными. Осталось доказать, что можно сединить 2N точки описанным методом(*).
Алгоритм построения для N=(p-1)/2, где p-простое.
Хотя для общего доказательства нам этот алгоритм не понадобиться, с практической точки зрения он полезен для многих небольших N.Пусть 2N=p-1 (p-любое нечетное простое).Воспользуемся проведенной нумерацией точек и запишем мултьтипликативную таблицу вычетов по модулю p.(p-1)*(p-1)(Как таблица умножения, только результат произведения берется по модулю p)
Пример p=5 (N=2)
1 2 3 4
2 4 2*3=6=1(mod 5) 2*4=8=3(mod 5)
Пример соединения по жтой таблице приведен на рисунке 2.
Теперь проведем доказательство что для любого нечетного простого p  соединение точек так как они стоят в верхних N строках таблицы (P-1)(P-1) дает искомое построение, если каждому цвету из N соединять последовательно N точек так как дано в таблице (соседние числа из Nй строчки соединяем N-м цветом. ((p-1)=2N).
Рассмотрим первые N строк таблицы: каждая строка показывает, как соединять точки линиями однго цвета (ведь в каждой строчке перстановка чисел от 1 до 2N , т.к. p- простое).Действительно, если в k-й строке, в столбцах g и f ,стоят одинаковые числа, то
Gk=t(mod p), fk=t(mod p), тогда (f-g)k делится на простое p что неверно т.к. f-g и k меньше p.(поэтому же нет и нулей).-Если в строке числа х и y стоят рядом, то надо соединить точки с номерами х и y. Тогда всего имеем N(2N-1) линий- по 2N-1 линии каждого цвета из N цветов (Напоинаю, что каждая из первых N строк показывает как соединять точки одним из N цветов- все строски для линий разных цветов). Мы показали, что в каждой из N первых строк таблицы стоит перестановка чисел 1,2,,,,2N, то есть мы имеем N отрезков(топологически) разных цветов, каждый из которыз проходит через все 2N точки.
Осталост доказать, что мы не проводим дублирующих связей – два или более раз не соединяем одну пару точек. Предположим обратное: в строке f, столбце a стоит число х, в соседнем столбце справа а+1 стоит y. Предположим, что где-то в строке g!=f  x и y стоят рядом, тогда возможны 2 варианта 1) y стоит справа от х 2) слева от х. В случае 1 x cтоит в каком то столбце b, a y – в b+1. Тогда fa=x(mod p) f(a+1)=y (mod p), откуда f=y-x(mod p).
Gb=x(mod p)  g(b+1)=y(mod p) Откуда g=y-x(mod p) тогда g=f (mod p),  значит g=f  так как оба меньше p. Противоречме с g!=f. Во 2м случае также f=y-x(mod p) , a для g получим g=x-y  (mod p), сложив, получим что f+g делится на P невозможно, так как мы берем только перые (P-1)/2 строк, значит сумма будет не более P-1.Доказано.
Итак мы провели N(2N-1) связей, причем каждый цвет отрезком(топологически) проходит через все  2N  точки , и не проводили дублирующих линий. То есть мы построили конструкцию (*), описанную в Общей конструкции, где было доказано, что такое соединение позволяет соединить все 4N точки, так что каждая связана с остальными.
Удвоение N (множитель 2^k, k-любое натуральное).
Покажем теперь, как можно удваивать N (таблицу). Рассмотрим в этой таблице произвольную строку (она пишется abcd….wxyz  , причем количество чисел четно ,т.к. 2N четно) и отразим ее: например у вас есть строка 123456 тогда допишем ее 123456|789 10 11 12,тогда пусть 1 составляет пару с 12, 2- с 11 итд симметрично относительно конца (число s – с 4N+1-s итд и было 2N чисел (1....2N).Пара симметрична относительно черты после 2N-го числа, 123456|789 10 11 12.Если 1....|…..12 –пара, то 12...|….1 – обратная пара
(определение; если ...a…|...4N+1-a… -пара, то...4N+1-a…|...a…- обратная пара   )
Тогда если имеетмч строчка ab…v, то (опред.) запись ab…v| (с вертикальной чертой) будет означать удвоенную по длине строчку ab...v|4N+1-v,….,4N+1-a-новая строчка получена из исходной построением пар, симметричных относительно |.
Пусть мы имели N строк вида ab…wxyz.Удвоим эти строки достроив пары ,получим N строк длины 4N ( а надо 2N строк длины 4N).Используем обратные пары: если пара обозначается f…| то обратная – f `…| , тогда если вначале были строки ab…wxyz,
То мы делаем строки zy ` x w `….| -записываем в обратном порядке чередующимися парами- сначала простой, затем обратной, простой, итд. Пример- было 123456- стало
6 8 4 10 2 12| 1 11 3 9 5 7. Теперь у нас 2N строк по 4N чисел (1...4N), что составляет 2N(4N-1) связей. Как следует из доказательства для общего построения, если на 2F точек приходится F(2F-1) связей (без двойных , с F отрезками, проходящими через все 2F точки), то каждая из 2F  точек соединена с остальными. У нас F=2N. Осталось доказать, что между точками не возникает двойных связей (то, что встроках набор от 1 до 4N следует из построения пар и это отрезки).Остальное соединение всех 8N точек аналогично.Будем сначала проводить рассуждения для связей, не разделенных знаком| (все связи, которые разделяются знаком | имеют вид a a ` (пара) и a ` a(обр. Пара) и встречаются только там).Действительно, связи вида ab (включают ab и ba) не встретятся более 1 раза, т.к. такие связи есть только встроках вида ab…wxyz|….(*)(за a и b здесь стоят конкретные числа из начальных строк, а за a ` b `-симметричные им), а посследовательности ab….wxyz идентичны исходным, где связь ab была только раз.(имеется ввиду что связь ab не повторяется во всей совокупности 4N строк). Для связей вида a ` b ` (из строк (*) после знака |)заметим, что если они повторяются то повторяются и ab, что неверно. Рассмотрим теперь строки вида zy ` xw ` …|…(**).Докажем неповторимость для связей вида fg` (где f!=g)(для g `f аналогично).Они находятся только в строках вида (**). Если связь fg` встречается несколько раз , то в исходных строках fg  тоже повторяются (по построению), что неверно, т.к. Левая и правая часть (**) являются изначальными последовательностями (вида ab…xyz) c точночтью до знаков ` и, возможно, записаны в обратном порядке. Нам осталось доказать что не повторяются связи вида a a` и a` a. У нас всего 2N строк и чисел a,b,…,z тоже 2N. Пусть какая-то начальная строка имеет вид s….u, тогда вдвух новых строках,которые из нее получатся, у знака | будут стоять числа s,s` и u,u` (по построению). Если теперь в новых строках у знака | будет не раз стоять какое-то число a,  то в начальных строках оно больше 1 раза было с краю, но тогда точка с номером a была связана менее чем с 2N-1 точкой-(связана с 2 точками когда внутри массива и с 1й-когда на краю) противоречие.Доказано.
Утроение N (множитель 3^k, k-любое натуральное).
По аналогии с удвоением можно получить утроение любого набора строк.
Ввеем обозначения. Исходные строки abc..yz будем обозначать a1b1c1…y1z1,
Если 1 означает строку abc…yz, то запись 123 будет означать строку
A1b1c1…y1z1|a2b2c2….y2z2|a3b3….y3z3, где числа в средней строке получаются аналогично тому как для удвоения в(*) и в 3й по аналогии,
Например 12|34|56, таким образом что в строке 1 стоит набор от 1 до 2N, в строке обозначаемой 2 –набор от 2N+1 до  4N, в строке ,обозначаемой 3 – от 4N+1 до 6N, и стоящие соответсвенно с определением пар, как в удвоении, ориентируясь на исходную строку.
Алгоритм утроения N зашифрован в следующей таблице:
1(2,3)
2(3,1)
3(1,2)
Запись типа (2,3) означает перемешивание строк 2 и 3 по строго определенному правилу,
А именно 1(2,3)=a1b1…y1z1|z2y3x2…|…..y2z3
Пример если 1=12, то имеем a1b1a2b2a3b3=123456,
Тогда 1(2,3)=12|45|36     1(32)=126354
           2(3,1)=34|61|52     2(13)=342516
           3(1,2)=56|23|14     3(21)=564132
Доказательство по аналогии со случаем для удвоения.(что нет повторов)
Построение множителей вида 5^k, итд p^k, где p-простое ,k-любое натуальное.
Теперь покажем, как строить множитель для любых нечетных простых чисел, таким образом будут охвачены все N, т.к. любое N можно разложить на простые сомножители.
Без ограничения общности покажем алгоритм построения магического куба для случая упятерения (нужен правильный куб 5х5).
A. Сначала в первый столбец матрицы 5х5 вписываем ряд 1,...5  (1....p для других p)



1
2
3
4
5

Так сохраняются исходные связи.
B приплюсовываем 1 (по модулю p!) к начальному числу в строке и ставим его в конец с закрывающей скобкой
1 2)
2 3)
3 4)
4 5)
5 1)

С. Выпишем матрицу возможных комбинаций
1(1,2)(1,3)(1,4)(1,5)
2(2,1)(2,3)(2,4)(2,5)
3(3,1)(3,2)(3,4)(3,5)
4(4;1)(4,2)(4,3)(4,5)
5(5,1)(5,2)(5,3)(5,4)

Все они должны быть в таблице.ю но ьез повторов как (5,1) и (1,5) ,чтобы не было 2х связей и все множества д.б. перемешаны.

D Приплюсовываем 1 по модулю 5 к крайне правой 1й незаполненной строчке

1 (3 2)
2 3)
3 4)
4 5)
5 1)

Приписываем (4,5) или (5;4) к 1й строчке
1 (4-5 5-4) (3 2)
2 3)
3 4)
4 5)
5 1)
E вычеркиваем (23) и (45) из таблицы (лучше писать наддиагональ только)
1(12)(13)(14)(15)
2              (24)(25)
3              (34)(35)
4
G
Аналогично прибавляем к следующей строчке 1 по модулю 5 если разрешено, если нет- 2 итд.
1 45 54 (3 2)
2 15 51 (4 3)
3 4)
4 5)
5 1)

Итерация E
Вычеркиваем 51 и 34
1(12)(13)(14)
2              (24)(25)
3                (35)
4
Итерация F
Т.к. 1 прибавить нельзя прибавляем 2 по модулю 5
1 45 54 (3 2)
2 15 51 (4 3)
3 25 52 (1 4)
4 5)
5 1)
Итерация E
Вычеркиваем 25 и 14
1(12)(13)
2              (24)
3                (35)
4
Итерация F
1 45 54 (3 2)
2 15 51 (4 3)
3 25 52 (1 4)
4 12 21 (3 5)
5 1)
Итерация E
Вычеркиваем 12 и 35
1(13)
2              (24)
3               
Итерация F
1 45 54 (3 2)
2 15 51 (4 3)
3 25 52 (1 4)
4 12 21 (3 5)
5 24 42 (3 1)

Итерация H
Окончательно расставляем скобки
1 (4 5) (3 2)
2 (1 5) (4 3)
3 (5 2) (1 4)
4 (1 2) (3 5)
5 (2 4) (3 1)

Надо проверить по границам.условия.
Доказательство корректной работы алгоритма несложно.