2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 проблема 4 красок
Сообщение06.12.2006, 18:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение06.12.2006, 19:55 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение06.12.2006, 20:51 
Экс-модератор
Аватара пользователя


23/12/05
12065
Wikipedia писал(а):
К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту.

 Профиль  
                  
 
 
Сообщение06.12.2006, 20:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Можно обойтись 3 цветами
Сообщение07.12.2006, 08:52 


24/05/05
278
МО
Вот пример способа заполнения досок $2n\times 2n$ для $n = 1,2...6$
Изображение

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

 Профиль  
                  
 
 Re: Можно обойтись 3 цветами
Сообщение07.12.2006, 12:21 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
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 строчку.

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

 Профиль  
                  
 
 этого я не обещал
Сообщение07.12.2006, 20:11 


24/05/05
278
МО
worm2 писал(а):
sceptic писал(а):
Вот пример способа заполнения досок...

Как насчёт раскраски такой доски в 3 цвета:
Изображение
:?:


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

 Профиль  
                  
 
 
Сообщение08.12.2006, 11:49 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
Извините, я Вас неправильно понял...

 Профиль  
                  
 
 Re: Можно обойтись 3 цветами
Сообщение08.12.2006, 11:56 
Заслуженный участник
Аватара пользователя


11/01/06
3828
worm2 писал(а):
RIP писал(а):
Данный (очень) частный случай допускает док-во в 1 строчку.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group