Замкнутая ломаная на целочисленной решётке

[Xenia1996]

Эту задачу я придумала сама только что по мотивам одной старой олимпиады.

На целочисленной двумерной решётке дана замкнутая ломаная, не имеющая самопересечений и не проходящая ни через один узел. В области, которую ограничивает эта ломаная, расположено не менее 2011 узлов.
В каком наименьшем числе точек данная ломаная может пересекать линии решётки?

[Sonic86]

Параллелограмм $(0;0), (45;1), (46;46), (1;45)$ содержит в себе $45^2-2=2023$ точек, каждая его сторона пересекается лишь с $45$ прямыми решетки. Значит наименьшее число точек пересечения не больше $4 \cdot 45 = 180$...

Upd: точку $(0;0)$ меняем на $(0;2)$ - уже $179$....
Upd2: $(0;1),(45;0),(46;45),(1;46) \to 176$...

[Xenia1996]

Sonic86 в сообщении #402108 писал(а):

Параллелограмм $(0;0), (45;1), (46;46), (1;45)$ содержит в себе $45^2-2=2023$ точек, каждая его сторона пересекается лишь с $45$ прямыми решетки. Значит наименьшее число точек пересечения не больше $4 \cdot 45 = 180$...

Upd: точку $(0;0)$ меняем на $(0;2)$ - уже $179$...

И с каких-таких пор "доказать" и "привести пример" - это одно и то же?
А как может быть 179? Это же нечётное число! Ведь я написала, что ломаная не проходит ни через один ухел...

[Sonic86]

(Оффтоп)

Xenia1996 писал(а):

И с каких-таких пор "доказать" и "привести пример" - это одно и то же?

я не доказываю. Надо хотя бы минимум нащупать. А потом уже доказательство, а потом его оптимизировать - боюсь бензина не хватит...

-- Чт янв 20, 2011 14:30:56 --

Xenia1996 писал(а):

А как может быть 179? Это же нечётное число? Ведь я написала, что ломаная не проходит ни через один ухел...

ааа! я неверно понял задачу! Мне показалось, что узлы ломаной - точки решетки

[Xenia1996]

Sonic86 в сообщении #402113 писал(а):

(Оффтоп)

Xenia1996 писал(а):

И с каких-таких пор "доказать" и "привести пример" - это одно и то же?

я не доказываю. Надо хотя бы минимум нащупать. А потом уже доказательство, а потом его оптимизировать - боюсь бензина не хватит...

(неподалёку от моего дома бензоколонка есть )

[Sonic86]

Тогда все гораздо легче. Рисуем 2011 точек и берем их выпуклую оболочку $L$. Возьмем $P=2(L_x+L_y)$, где $L_x, L_y$ - длины проекций $L$ на оси (они целочисленные). Поскольку $\sqrt{2011}=45- \varepsilon$, то $L_x \geq 45$ (случай $L_y \geq 45$ симметричен ему). Если $L_y \leq 44$, то в $L$ не влезет 2011 точек, а при $L_y = 45$ влезет. Значит $L_x, L_y \geq 45$. Докажем, что равенство достигается. Выкладываем в квадрат $45^2$ точек, $45^2 > 2011$. Наконец, $L$ обрисовываем достаточно близкой ломаной, тогда число ее пересечений с решеткой будет совпадать с $P$, т.е. $180$

Смысл в том, что площадь прямоугольника максимизирется (периметр минимизируется) на квадрате.

-- Чт янв 20, 2011 14:44:15 --

(Оффтоп)

Xenia1996 писал(а):

неподалёку от моего дома бензоколонка есть :-))

Смешно, ценю Ваш юмор :-)

З.Ы. А вот если узлы ломаной принадлежат решетке с сохранением остальных условий, тогда задача посложнее будет...

-- Чт янв 20, 2011 14:49:47 --

Правильно хоть решил? (я часто ошибаюсь)

[Xenia1996]

Sonic86 в сообщении #402121 писал(а):

Правильно хоть решил? (я часто ошибаюсь)

У меня, вроде, тоже 180 вышло. Классическая задача на минимум и максимум, вид сбоку