2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение15.06.2017, 19:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328
yk2ru
Это Вы комментируете попытку Sender? Да он попытался именно так, при этом обостряются все прямые углы на гранях, но все диагональные прямые (24 угла) остаются прямыми. Он же сам и заметил это.

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение16.06.2017, 15:01 


03/10/06
826
grizzly в сообщении #1225801 писал(а):
диагональные прямые (24 угла) остаются прямыми.

А если брать не куб, а близко к кубу фигуру, чтобы каждая грань была похожа на трапецию, несильно отличающуюся от квадрата. Будут два острых угла, и два тупых, близких к 90 градусам. А по четвёртому измерению двигать те точки, к которым примыкают тупые, но почти прямые углы, с целью их уменьшения. Может получится?

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение16.06.2017, 15:33 
Заслуженный участник
Аватара пользователя


09/09/14
6328
yk2ru в сообщении #1226138 писал(а):
Может получится?
Я думаю, что нет. Но было бы здорово, если бы Вы попробовали -- а вдруг? (Если бы я думал, что получится, я бы и сам не поленился попробовать :)

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение24.06.2017, 15:00 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Бывает понимание типа просветления, а бывает и так, что варится какой-то вопрос в голове на медленном огне и со временем оно само приходит -- понимание. Дофаминовая награда за последнее обычно небольшая (чаще наоборот, испытываешь разочарование -- почему, мол, раньше не догадался), но в сухом остатке одно и то же.

Я посмотрел вот на это:
grizzly в сообщении #1225523 писал(а):
Вершина -- точка "сверху" по центру, как обычно (про неё можно забыть -- она имеет большой запас прочности).
и подумал, а что будет, если поэксплуатировать имеющийся запас прочности. Выбросить девятую точку и построить из восьми точек такое остроугольное множество в $R^4$, у которого минимизирован наибольший угол.

Получился неожиданно красивый симметричный многогранник (использован только один параметр $792=1000-208; 104=208/2$; я теперь работаю в целочисленной решётке):
Код:
    a1     a2   a3    a4    a5    a6     a7    a8
x  208  792     0    1000   0     1000   208  792
y  208    0   792    1000   0     208   1000  792
z  208    0     0    208    792   1000  1000  792
t  792    0   104    208    208   104     0   792
Собственно, теперь мне понятно, как были взаимосвязаны числа по четвёртой координате в моём примере на 9 точек (на непонимание этого момента я несколько раз жаловался раньше).

А с $R^5$ всё настолько сложнее, что у меня время от времени возникают сомнения в "формуле grizzly" :D Но я ещё попытаюсь.

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение02.07.2017, 23:34 
Заслуженный участник
Аватара пользователя


09/09/14
6328
heptagon в сообщении #1223983 писал(а):
Удалось ли Вам достичь какого-либо прогресса (относительно 12 точек) в размерности 5?

Теперь да. На сегодня имеем новый мировой рекорд из 16 точек.
Код:
a=( 120,         120,         120,         120,         750    );
b=( 999,           1,           1,           1,           0    );
c=( 0.0001,    999.9999,      0.0001,      0.0001,      63.443   );
d=( 999.99999, 999.99999,        0,           0,        64.073   );
e=( 0,            0,        999.999989,     0.000009,   64.074   );
f=( 999.99999,    0,        999.999999,     0.000009,   64.076   );
g=( 0.000008,   999.99999,   999.999988,    0.000009,   64.218   );
h=( 999.999989,   1000,        1000,        0.000009,   64.075   );
                                                                               
k=( 0.000011,   0,         0,         999.999991,   64.075   );
l=( 999.999992, 0.00001,  0.000012,   999.999991,   64.218   );
m=( 0.00001,   1000,      0.000001,   999.999991,   64.076   );
n=( 1000,      1000,      0.000011,   999.999991,   64.074   );
o=( 0.00001,   0.00001,    1000,      1000,         64.073   );
p=( 999.9999,  0.0001,    999.9999,   999.9999,     63.443   );
q=( 1,         999,        999,       999,          0        );
r=( 880,       880,        880,       880,          750      );
Каждая точка по первым 4-м координатам достаточно близко "привязана" к вершинам 4D куба, одна из главных диагоналей которого проходит через точки (0,0,0,0) и (1000, 1000, 1000, 1000). Собственно, это и даёт 16 точек.

grizzly в сообщении #1224015 писал(а):
И да, я не пытался побить рекорд в 12 точек -- я пока надеюсь найти все 17.
Ну что же, нацеленность на максимальный результат, не размениваясь по мелким рекордам, себя оправдала (это только у легко- и тяжело- атлетов есть смысл рекорды бить по 1 копейке :)

В этом раскладе не хватает ещё одной точки -- 17-й. Увы, с этим вышла заминка. С самого начала я начал формировать основу "пирамидки" и использовал весь запас прочности (см. мои предыдущие сообщения с туманными пояснениями). Теперь вершинка пирамидки совсем чуть-чуть, но не вписывается. И это не лечится мелкими подвижками -- нужно начинать строить всю конструкцию сначала. (А всего-то нужно было взять в самой первой строчке числа поменьше -- именно с этой точки я начинаю построение.)

Теперь мне переделывать ради 17-й точки уже не хватает внутренней мотивации, поскольку ответ для меня очевиден, и в общей формуле $|S|=2^{d-1}+1$ сомнений не осталось. Тут следует уточнить: сомнений не осталось не только потому, что я нашёл пример и в $R^5$. Дело в том, что при самом построении примера чувствуется, что в $R^5$ происходит то же, что и в $R^4$ -- каких-то качественно новых сложностей не возникает, углы обзора всегда остаются, хотя и неуклонно сужаются. Легко видеть, что решение обладает некой симметрией (как и в $R^4$). Должны быть ещё и другие, внутренние, симметрии (см. моё сообщение выше), но я их здесь пока не разгадал. Ещё я предчувствую разницу между симметриями пространств чётных и нечётных размерностей, но это вряд ли может быть интересно за пределами танка :)

Но это всё лирика, а формула требует доказательства. И я почему-то думаю, что доказательство снизу будет найдено быстрее и проще, чем сверху.

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение03.07.2017, 01:05 


10/06/17
6
grizzly, я проверил Ваш пример. Поздравляю Вас, это просто фантастика!

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение03.07.2017, 12:53 
Заслуженный участник


04/03/09
910
grizzly

Заметил интересную штуку. Если взять ваши примеры для 4-х (тот, который "некрасивый") и 5-мерного пространства, посчитать у точек "центр масс", а потом расстояния от центра масс до этих точек, то расстояния получаются практически одинаковыми. Т.е. получается, что точки расположены на $(n-1)$-мерной гиперсфере. Более того, расстояния от каждой точки до ближайшего соседа тоже получаются примерно одинаковыми. Еще более того, в последнем примере у каждой точки ровно 4 соседа на расстоянии менее 1200.
Таким образом, построение таких примеров сильно смахивает на задачу о контактном числе, где тоже требуется распихать более-менее равномерно точки по гиперсфере.

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение03.07.2017, 13:16 
Заслуженный участник
Аватара пользователя


09/09/14
6328
12d3
Очень интересные наблюдения. Я немного отдохну и тоже посмотрю на всякие внутренние симметрии. Кое-что из замеченного -- это артефакты поискового метода, но не всё. Например, привязка точек к углам 4D-куба сама по себе означает некую близость к условной гиперсфере, но если эта близость действительно окажется лучше ожидаемой, это даст что-то новое в понимании.

Заодно уточню, что попытки просто посмотреть, как мои программы и методы поиска будут вести себя в $\mathbb R^6$ ни к чему не привели -- там оно совсем не шевелится. Думаю, что построение других примеров вряд ли можно будет считать "разумной деятельностью" :D , но вот попытаться найти симметрии, понять и обобщить до уровня формулы было бы интересно.

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение05.07.2017, 17:08 
Заслуженный участник
Аватара пользователя


09/09/14
6328
grizzly в сообщении #1231121 писал(а):
В этом раскладе не хватает ещё одной точки -- 17-й. ... И это не лечится мелкими подвижками -- нужно начинать строить всю конструкцию сначала. (А всего-то нужно было взять в самой первой строчке числа поменьше -- именно с этой точки я начинаю построение.)
Немного отдохнул и решил закончить, раз взялся. Добавил 17-ю точку -- строго по указанному выше сценарию (как я это знал -- сам удивляюсь :) Оказалось много проще, чем я думал. Пример под катом:

(ПРИМЕР 17 ТОЧЕК)

Код:
a=(  40,          40,          40,          40,         500    );
b=( 999,           1,           1,           1,           0    );
c=( 0.0001,    999.9999,      0.0001,      0.0001,      64.143   );
d=( 999.99999, 999.99999,        0,           0,        64.773   );
e=( 0,            0,        999.999989,     0.000009,   64.774   );
f=( 999.99999,    0,        999.999999,     0.000009,   64.776   );
g=( 0.000008,   999.99999,   999.999988,    0.000009,   64.918   );
h=( 999.999989,   1000,        1000,        0.000009,   64.775   );
                                                                               
k=( 0.000011,   0,         0,         999.999991,   64.775   );
l=( 999.999992, 0.00001,  0.000012,   999.999991,   64.918   );
m=( 0.00001,   1000,      0.000001,   999.999991,   64.776   );
n=( 1000,      1000,      0.000011,   999.999991,   64.774   );
o=( 0.00001,   0.00001,    1000,      1000,         64.773   );
p=( 999.9999,  0.0001,    999.9999,   999.9999,     64.143   );
q=( 1,         999,        999,       999,          0        );
r=( 960,       960,        960,       960,          500      );

s=( 455,       455,       455,         455,         -995   );


-- 05.07.2017, 17:17 --

heptagon
Буду благодарен, если проверите ещё и этот набор (не то чтоб я сомневался в своих программах, но перестраховаться в этом деле лишним не будет).

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение05.07.2017, 17:56 
Заслуженный участник


04/03/09
910
grizzly
Проверил, все верно.

 Профиль  
                  
 
 Posted automatically
Сообщение05.07.2017, 18:57 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Математика (общие вопросы)»
Причина переноса: тема перенесена в более подходящий раздел

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение20.07.2017, 20:18 


13/11/15
31
В архиве появился новый препринт московского школьника, с которого началась тема.
https://arxiv.org/pdf/1707.04829.pdfОценка снизу улучшена, хотя до высказываемой
уважаемым grizzly гипотезы не дотягивает

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение20.07.2017, 21:38 
Заслуженный участник
Аватара пользователя


09/09/14
6328
a1981
Спасибо, очень интересная работа! На этот раз техника выглядит немного сложнее (это впечатление от первого просмотра; конечно я ещё не вникал в детали).

Хотелось бы сказать, что я тоже не сидел сложа руки в поисках закономерностей и явного алгоритма построения. Но так принято говорить только если получают какие-то результаты, а не просто тратят время :D Увы, существенных продвижений у меня нет. Поэтому меня особенно радуют очередные результаты Дмитрия -- вдруг они и мне чем-то помогут (как это было в прошлый раз, когда здесь всё завертелось :)

 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение31.07.2017, 10:51 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Более-менее разобрался в последней работе Дмитрия. Да, он нашёл интересный способ раздваивать точки при каждом увеличении размерности. И в каком-то смысле он выжал из этого способа максимум, я думаю (начиная с $\mathbb R^2$ точки раздваиваются "жадным" алгоритмом). Я думаю, что для следующего прорыва нужно будет отказаться от "жадности" (но не от технических идей -- они ещё сослужат службу, наверно).

Я вложил один из своих инструментов (основной) поиска ОМ. Он работает в пространстве $\mathbb R^4$. Выкладываю как есть, без подробных описаний (минимум полезных комментариев есть внутри -- основное поле деятельности для пользователя между 225 и 290 строками). Инструмент вообще был написан "под себя" (программист не я, это всё группа поддержки) и предназначался для творческого поиска решений, поэтому в нём осели какие-то малопонятные механизмы -- на них можно не обращать внимания. Если кого-то заинтересует, постараюсь ответить на возникающие вопросы. Имеется также аналогичный вариант для $\mathbb R^5$, который ищет ОМ из $2^4$ точек, я его тоже выдам, если будет спрос :)

В дальнейшем планируется апгрейд с несколькими оптимизациями и украшением кода (сворачиванием циклов в рекурсии и т.п.). Я тогда это тоже выдам. Если вдруг кто-то при использовании сможет добиться лучшей эффективности, просьба делиться.

-- 31.07.2017, 10:54 --

Это всё работает миллисекунды. А значит в 80-х вполне реально было посчитать на тех компах. Очень странно, что столько людей тогда прошло мимо.


Вложения:
acute_sets.cpp [18.24 Кб]
Скачиваний: 430
 Профиль  
                  
 
 Re: Улучшено (?) решение Эрдёша по остроугольным треугольникам
Сообщение31.07.2017, 11:17 


14/01/11
3019
grizzly в сообщении #1236964 писал(а):
сворачиванием циклов в рекурсии и т.п.

Вот как раз сворачивание циклов в рекурсии может негативно сказаться на быстродействии, как мне кажется.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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