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

Задача

9 марта 2008 года, 20:44

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

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

7 прямых

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

Поделиться

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

Читайте также

Головоломка Арнольда
Постоянные читатели помнят, что мы с коллегами по учебе лет 10 назад занимались задачей Арнольда. В ней остались открытые вопросы, и я недавно решил к ним вернуться.
2020
Задача о педантичном пассажире
В недавней поездке наблюдал, как люди рассаживаются в автобусе.
2023
Как додуматься до решения олимпиадной задачи?
Я иногда решаю «для себя» какие-нибудь сложные задачи по физике или математике.
2021
Автоморфные числа
В этой заметке мы исследуем элементарными школьными методами свойства интересного множества чисел, которые называют автоморфными.
2005
Формула Эйлера и приближенные методы
Илья Бирман в заметке о числах π и e написал об их связи со мнимой единицей:
2012

Комментарии

#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. пишет:
Вот интересная задачка:

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

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


Формулы на латехе: $$f(x) = x^2-\sqrt{x}$$ превратится в $$f(x) = x^2-\sqrt{x}$$.
Выделение текста: [i]курсивом[/i] или [b]жирным[/b].
Цитату оформляйте так: [q = имя автора]цитата[/q] или [q]еще цитата[/q].
Других команд или HTML-тегов здесь нет.

Записи