проблема 4 красок

[RIP]

Пусть шахматная доска размера $2n\times2n$ разбита на доминошки $1\times2$. Докажите, что можно так покрасить доминошки в 4 цвета (каждую доминошку в 1 цвет), что доминошки с общим куском границы (общая вершина не считается) будут покрашены по-разному.

[Capella]

Подобная задача есть так-же и про глобус. Доказать, что нужно использовать 4 цвета для закраски стран, при этом нельзя чтобы страны "одного цвета" были соседями.
Условие чуть посложнее, чем у Вас, т.к. одна страна может иметь $n$ соседей (количество соседей доминошки изначально ограничено до 4).
Кстати, эта задача, похоже, возникла из области информатики... Есть специальный алгоритм, возволяющий находить решение.

[photon]

Wikipedia писал(а):

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту.

[RIP]

О проблеме 4 красок я знаю, отсюда и название темы. Данный (очень) частный случай допускает док-во в 1 строчку.

[sceptic]

Вот пример способа заполнения досок $2n\times 2n$ для $n = 1,2...6$


Каждая доска вырезается, начиная с верхнего левого угла рисунка.
Эта укладка очевидным образом продолжается на доски $2n\times 2n$ для любого $n.
Надеюсь, нет нужды словесно описывать правило укладки доминошек.

[worm2]

sceptic писал(а):

Вот пример способа заполнения досок...

Как насчёт раскраски такой доски в 3 цвета:
Изображение утеряно (http://img86.**invalid link**/img86/3419/dominonf1.gif)


Добавлено спустя 1 час 2 минуты 18 секунд:

Раскрасим "чёрные" клетки доски следующим образом:

Изображение утеряно (http://img139.**invalid link**/img139/849/ ... ardru1.gif)

Каждая доминошка закрывает ровно одну "чёрную" клетку. В цвет этой клетки мы её и покрасим. Очевидно, две доминошки одного цвета никак не смогут граничить друг с другом (ну разве что только вершинами).

Добавлено спустя 2 минуты 12 секунд:

RIP писал(а):

Данный (очень) частный случай допускает док-во в 1 строчку.

Если бы я этого не знал, доказывал бы гооораздо дольше :)

[sceptic]

worm2 писал(а):

sceptic писал(а):

Вот пример способа заполнения досок...

Как насчёт раскраски такой доски в 3 цвета:

Ваше покрытие доминошками доски $4\times 4$ доминошками не раскрашиваемо в 3 цвета. Я разве утверждал, что любое покрытие доски $2n\times 2n$ доминошками $2\times 1$ раскрашиваемо в 3 цвета?

[worm2]

Извините, я Вас неправильно понял...

[RIP]

worm2 писал(а):

RIP писал(а):

Данный (очень) частный случай допускает док-во в 1 строчку.

Если бы я этого не знал, доказывал бы гооораздо дольше

Однажды на Всероссийской олимпиаде я смог решить задачу только потому, что она была первая в списке (она казалась мне трудной, но первой же обычно ставят простые )
P.S. Правильнее было бы сказать "док-во в 1 рисунок", но это было бы уж слишком большая подсказка.