Сайт Романа ПарпалакаБлог20080309

Задача

На плоскости проведены n прямых, разбивающих ее на области. Они раскрашиваются в шахматном порядке: области, имеющие общие стороны, должны быть покрашены в разные цвета. Чему равна максимальная разность между числом черных и белых областей?

PS. Для заинтересовавшихся этой задачей приведу одну картинку для семи прямых:

7 прямых

Разность между числом черных и белых областей на этом рисунке — 7. Расположение прямых, дающее такую разность, не единственное, но вычисления на компьютере показали, что улучшить данный результат нельзя.

9 марта 2008 года, 20:44     математика
Смотрите также:  Исследование на миллион

Заколебал ты! Ctrl Adobe Air

Поделиться

Комментарии

#1. 9 марта 2008 года, 22:31. пишет:
n произвольных прямых? Разве в этом случае минимальное требование не 4 краски?
#2. 9 марта 2008 года, 23:06. пишет:
Нет, 4 краски — это из другой задачи, когда плоскость просто разбивается на совершенно произвольные области с кривыми границами:

http://ru.wikipedia.org/wiki/Проблема_четырех_красок

А когда плоскость разбивается прямыми, можно доказать, что двух цветов достаточно.
#3. 10 марта 2008 года, 04:35. пишет:
Да, ступил. Достаточно инвертировать цвета с одной стороны от новой прямой, чтобы восстановить инвариант.

Есть интуитивное подозрение, что максимальная разница — 1, как формально доказать пока не знаю.
#4. 10 марта 2008 года, 12:13. пишет:
Да, доказательство существования раскраски именно такое. А предположение о том, что ответ есть единица — неверное :)

Я добавил к записи для примера картинку, получающуюся для 7 прямых. Там разность — 7.
#5. 6 мая 2008 года, 21:04. пишет:
Вот интересная задачка:

Некоторые из участников математической олимпиады являются друзьями. Если один участник является другом второго, то второй является другом первого. Назовем группу участников компанией, если любые двое из них друзья. (В частности, любая группа менее, чем из двух участников, является компанией.) Количество членов компании назовем ее размером.
Известно, что в данной олимпиаде наибольший размер компании является четным числом. Доказать, что участников можно разместить в двух комнатах так, что наибольший размер компании, находящейся в одной комнате, равен наибольшему размеру компании, находящейся в другой комнате.

Оставьте свой комментарий

Ваше имя:

Комментарий:

Для выделения используйте следующий код: [i]курсив[/i], [b]жирный[/b].
Цитату оформляйте так: [q = имя автора]цитата[/q] или [q]еще цитата[/q].
Ссылку начните с http://. Других команд или HTML-тегов здесь нет.

Сколько будет 66+9?

Записи