- master-sheff
- Постоялец
В этой теме решаем задачи. Чтобы поддерживать задачи на должном уровне, сперва решаем, предложенную автором задачу, а потом кто решит выкладывает свою и решаем ее и т.д. Всем известно, что великие мыслители тут не водятся, но хотя бы постарайтесь не писать того, что не относится к теме.
Задача:
Есть n прямых на плоскости такие, что никакие 3 не пересекаются в одной точке и никакие 2 не параллельны. Областями называются фигуры (многоугольники) конечной площади на которые эти прямые разбивают плоскость. Докажите, что для достаточно большого n можно покрасить 0.5*sqrt(n) прямых в красный цвет так, что не найдется ни одной области все стороны которой красные.
id-mikle
Тебе что ЕГЭ в школе мало было? Описание задачи почему-то именно его сразу напомнило.
master-sheff
В мое время ЕГЭ не было. А вообще, на сколько мне известно, там нет задач на доказателство.
AcManZ
>https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B… 1%D0%BE%D0%BA
Слышал звон да не знаешь где он? Причем тут проблема 4 красок? В задаче нет никаких подвохов, где требуется математика заведомо выше ваших познаний.
Пишите по теме или не пишите вовсе.
Не вижу ничего интересного в этой задаче. Похоже на обычную школьную задачу олимпиадного уровня, хотя с равным успехом может оказаться вариантом какой-нибудь проблемы тысячелетия на миллион долларов. Тема говно.
Моя версия такая: Сначала проведем красные прямые. Они образуют N/8 - (3*sqrt(N)/4 + 1 треугольников. Ну и оставшимися прямыми (которых у нас останется N - sqrt(N)/2 "порежем" эти треугольники. При достаточно большом N прямых у нас будет больше чем треугольников и потому даже если каждый треугольник резать одной прямой то все прокатит. Случай когда вместо треугольников четырехугольники и т.д. лень рассматривать, по-моему ясно что там еще лучше всё (т.е. областей которые надо порезать меньше).
——
И да, надеюсь я не угадал, потому что таких задач мне в жизни не придумать.
kipar
> Ну и оставшимися прямыми (которых у нас останется N - sqrt(N)/2 "порежем" эти
> треугольники.
Так прямые уже даны, разрешается их только красить, а не выбирать где и как их провести.
3 линии образуют 1 треугольник,
4 линии либо 1 либо 2
Каждая следующая линия может от (добавить 1 треугольник(ромб)) до (удвоить количество треугольников)
Линии каждая пересечется один раз с каждой, то есть это будет (n-1)*n/2 пересечений
То есть k = количество треугольников будет такое же - незамкнутые уходящие в никуда треугольники тоже посчитаем.
Если закрасить одну линию, она затронет n-1 пересечений, в которых будет n отрезков, то есть затронутых сторон треугольника
вторая линия так же затронет n треугольников
Третья линия так же затронет n треугольников, но для нее недоступен 4 треугольника (фигуры) исходящие из точки пересечения двух линий.
То есть 4 линии (являющиеся третьей стороной для трех 4 фигур) выпало.
L - количество закрашенных линий
Количество узлов к которых есть опасные треугольники будет (L-1)*L/2
Каждый узел порождает 4 опасных треугольника, третью или большую линию которых нельзя использовать.
То есть с каждой линией мы вычеркиваем (L-1)*L/2 узлов
Последнюю линию мы сможем поставить когда количество свободных узлов из k будет больше n - минимальное количество пересечений.
То есть если у нас закрашенных линий: L = 0.5*sqrt(n),
k - (L-1)*L/2 >= n
(n-1)*n/2 - (0.5*sqrt(n)-1)*0.5*sqrt(n)/2 >= n
0.5*n*n - 0.5*n - 0.5*n + sqrt(n) >= n
n*n - n + sqrt(n) >= n
n*n + sqrt(n) >= 2*n
хз че вышло. Три раза переписал. Наверняка бред.
Вообще все просто, я вчера что-то залез в дебри . Если есть m красных линий, они имеют m(m-1)/2 точек пересечения. Каждая точка пересечения запрещает к покраске до 4 линий. Итого, m линий запрещают 2m(m-1) линий. При m =sqrt(n)/2 получаем < n/2, т.е. мы сможем покрасить даже ещё одну линию, не то что эти покрасить.
А, ну и сами m линий надо учесть. Т.е. неравенство будет m+2*m*(m-1) < n или m+2m(m-1) < 4m*m.
в школе нарешался, сейчас лень
AcManZ
Честно говоря, ничего не понял.
>То есть с каждой линией мы вычеркиваем (L-1)*L/2 узлов
Почему? Точнее даже, что это означает?
>Последнюю линию мы сможем поставить когда количество свободных узлов из k будет больше n - минимальное количество пересечений.
Почему?
kipar
>ну и сами m линий надо учесть
Так в этом и проблема, что если покрасить какие-то m линий, то можно их так неудачно выбрать, что никакие другие линии не пересекают красные треугольники из выбранных линий. Или я не понял какой алгоритм выбора линий для покраски (тогда какой он?).
id-mikle
Красим одну две линии. Они создают одну точку пересечения. Вокруг этой точки пересечения может быть максимум 4 фигуры (треугольника или многоугольника). Для каждой из этих фигур мы красим одну из сторон в зеленый (для треугольника - единственную, для многоугольника - произвольную). Дальше выбираем любую другую (черную) и красим в красный, опять для каждой точки пересечения красим до 4-х линий в зеленый.
При этом алгоритме на m красных линий будет приходится не больше 2m(m-1) зеленых, что в сумме не превысит n, т.е. мы всегда сможем выбрать черную линию для покраски.
kipar
Да ты правильно решил! Я не ожидал, что есть такое тривиальное решение для 1/2*sqrt(n), таким методом выходит даже 1/sqrt(2) * sqrt(n), надо было сразу для sqrt(n) спрашивать.
Тема в архиве.