2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение18.12.2016, 02:33 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение19.12.2016, 11:55 


16/08/05
678
Считаем, что точки пронумерованы от 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).

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение19.12.2016, 15:40 


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 07:29 
Аватара пользователя


01/06/12
755
Adelaide, Australia
А почему для минимумов первая точка должна быть в (1,1)?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 12:56 


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 14:04 


25/08/12
89
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)...

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 19:11 


16/08/05
678
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]]

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 20:26 


16/08/05
678
а, нашлась 4

Изображение

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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.12.2016, 22:55 


25/08/12
89
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 00:20 
Аватара пользователя


01/06/12
755
Adelaide, Australia
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!

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 02:41 


25/08/12
89
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 05:45 


16/08/05
678
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 - получились такие варианты:

Изображение

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 10:20 
Аватара пользователя


10/11/12
119
Бобруйск
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?
Не чувствую гарантированных точек в этой задаче. Много контрпримеров на все маломальски логичные предположения.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 10:22 


25/08/12
89
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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 10:59 


16/08/05
678
Vovka17

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 100 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group