Al Zimmermann - Polygonal Areas

[dimkadimon]

Tomas Rokicki подключился к конкурсу и уже улучшил рекорд для $n=23$. Этот чувак реально крутой и выигрывает почти все - ждите новых рекордов.

[dmd]

Считаем, что точки пронумерованы от 1 до n.

Для максимумов гарантировано расположение первых трёх точек: (1||2, 1||2), (1||2, n-1||n), (n-1||n, n-1||n).

Для минимумов первая точка гарантированно (1, 1), и какая-то из средних точек (n-1||n, n-1||n).

Поэтому минимумы труднее.

[dmd]

Для максимумов вроде даже четвертая и последняя точки точно определены: (n-1||n, 2||3) и (n-2||n-1, 1||2). Плюс все остальные точки в максимумах группируются сравнительно плотно вдоль диагонали.

[dimkadimon]

А почему для минимумов первая точка должна быть в (1,1)?

Для максимумов думаю можно гарантировать 6 точек. Остальные не обязательно вдоль диагонали.

[dmd]

Ну вроде из соображений минимума площади. Но возможно чего-то не вижу.

А почему 6 точек для "рамки" максимумов? Три в углах квадрата и две в четвёртом угле, где вход во внутреннюю игольчатую структуру - 5 получается.

Интересно, что площадь любой иглы с основаниями на диагонали - меряется половинками единицы (1/2). Самая длинная такая игла имеет площадь 1/2. Тогда вроде получается, что теоретический минимум можно точно посчитать для любого n. И максимум значит тоже.

[Herbert Kociemba]

Due to Pick's theorem the theoretical minimum for all N for the area is N/2-1. I wonder for which N - independent from the N's given in the contest - this minimum is reached. Examples are N=5 with area=1.5 and N=10 with area=4 (a very beautiful solution)...

[dmd]

4.5 для N10, найти 4 не получается.

(Вольфраматика)

n = 10; t = Table[i, {i, n}];
pnt = {{8, 9}, {6, 5}, {9, 10}, {4, 6}, {7, 8}, {1, 1}, {2, 2}, {10, 7}, {5, 4}, {3, 3}}; pntc = Join[pnt, {pnt[[1]]}];
Graphics[{Green, Line[pntc], {PointSize[Large], Red, Point[pnt]}}, Frame -> True, GridLines -> {t, t}, GridLinesStyle -> Directive[Blue, Dotted]]

[dmd]

а, нашлась 4



Действительно красивая! И как сложно искать однако.

-- Ср дек 21, 2016 22:30:00 --

Симметрия точек видимо может наблюдаться при совпадении теоретического минимума с практическим.

[Herbert Kociemba]

You take the lines (10,3)-(6,6)-(3,8) and (9,4)-(2,9). The solution with the lines (10,3)-(3,8) and (9,4)-(6,6)-(2,9) is more beautiful because there also is an axial symmetry for the lines.

[dimkadimon]

dmd в сообщении #1178996 писал(а):

а, нашлась 4

В этом решении нет (1,1)!

dmd в сообщении #1178921 писал(а):

А почему 6 точек для "рамки" максимумов? Три в углах квадрата и две в четвёртом угле, где вход во внутреннюю игольчатую структуру - 5 получается.

У меня в одном углу (напротив входа) часто две точки получается, такое срезанный угол. Не знаю почему так.

Herbert Kociemba в сообщении #1178931 писал(а):

Due to Pick's theorem the theoretical minimum for all N for the area is N/2-1.

Excellent pick up Herbert!

[Herbert Kociemba]

dimkadimon в сообщении #1179057 писал(а):

У меня в одном углу (напротив входа) часто две точки получается, такое срезанный угол. Не знаю почему так.

Because it minimizes the "outer" area. With the points positioned at (3,2), (N-1,1), (N,N-1), (1,N) and (2,3) this area is 2N-1.
With the points positioned at (3,2), (N-1,1), (N,N-2), (N-2,N), (1,N-1) and (2,3) this area is 2N-1/2.

[dmd]

Herbert Kociemba в сообщении #1179040 писал(а):

You take the lines (10,3)-(6,6)-(3,8) and (9,4)-(2,9). The solution with the lines (10,3)-(3,8) and (9,4)-(6,6)-(2,9) is more beautiful because there also is an axial symmetry for the lines.

Да, с симметрией линий ещё красивее решение!

dimkadimon в сообщении #1179057 писал(а):

В этом решении нет (1,1)!

Да, Вы правы! Значит минимумы ещё сложнее, чем мне виделось.



Искал максимальную площадь внутри "рамки" из 5-ти точек для N17 - получились такие варианты:

[Vovka17]

dmd в сообщении #1178299 писал(а):

Для максимумов гарантировано расположение первых трёх точек: (1||2, 1||2), (1||2, n-1||n), (n-1||n, n-1||n)...
...вроде даже четвертая и последняя точки точно определены: (n-1||n, 2||3) и (n-2||n-1, 1||2)...

dimkadimon в сообщении #1178874 писал(а):

Для максимумов думаю можно гарантировать 6 точек...

Хорошо. Может это и работает.
Но вот я построил несколько решений. Вроде это максимумы для n=8, 9, 10. Гарантии на них не распространяются?

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

[Herbert Kociemba]

Herbert Kociemba в сообщении #1179084 писал(а):

With the points positioned at (3,2), (N-1,1), (N,N-2), (N-2,N), (1,N-1) and (2,3) this area is 2N-1/2.

Sorry, of course 2N-1.5

[dmd]

Vovka17

Хорошо. Возможно Вы и правы. Просто я исходил из того, что максимальная "рамка" из 5-ти точек больше максимальной "рамки" из 6-ти точек на 3/2 для любого n. А минимальная игла 1/2. Посмотрим, в общем.