2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Конкурс Изящные Графы
Сообщение22.09.2013, 15:30 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
У Al Zimmermann начался новый конкурс
http://www.azspcs.net/Contest/GracefulGraphs

Уже 20 человек набрали 25 баллов. Я надеюсь что самое интересное еще впереди и мы найдем улучшения. Иначе конкурс может стать довольно скучным.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение22.09.2013, 19:45 
Аватара пользователя


21/02/10
1594
Екатеринбург
Задачи с большой историей, очень неудобны для подобных конкурсов. Люди исследуют задачу уже несколько десятилетий. Как можно за три месяца придумать, что то кардинально новое?!

-- Вс сен 22, 2013 22:21:11 --

Цитата:
For instance, take a look at the example given in the challenge description. Instead of
(2,0), (0,4), (0,5), (2,5), (5,4)
one could simply use
(0,2,4,5)

Полностью согласен.
Зачем вводить описание сотен ребер, когда достаточно ввести N пометок вершин.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.09.2013, 02:04 


23/09/13
1
It looks like the contest is over. Another super-boring contest from Al. Thought that I will participate, these recent new contests have really low value.

Rank Score Contestant Last Improvement
1 25.00 Tomas Rokicki Palo Alto, California, United States 21 Sep 2013 17:37
2 25.00 Jarek Wroblewski Wroclaw, Poland 21 Sep 2013 18:35
3 25.00 Hugo Pfoertner Munich, Germany 21 Sep 2013 22:58
4 25.00 Hermann Jurksch Recklinghausen, Germany 22 Sep 2013 00:42
5 25.00 Dmitry Kamenetsky Adelaide, Australia 22 Sep 2013 02:46
6 25.00 Kevin Burfitt Melbourne, Australia 22 Sep 2013 05:29
7 25.00 Wes Sampson La Jolla, California, United States 22 Sep 2013 05:31
8 25.00 Igor Zhitnitsky Bronx, New York, United States 22 Sep 2013 05:59
9 25.00 Jon Schneider Princeton, New Jersey, United States 22 Sep 2013 07:39
10 25.00 Siegbert Steinlechner Leonberg, Germany 22 Sep 2013 09:32
11 25.00 Dan Banica Ploiesti, Romania 22 Sep 2013 09:45
12 25.00 Lucien Pech Zürich, Switzerland 22 Sep 2013 09:46
13 25.00 Esteban Crespi de Valldaura Madrid, Spain 22 Sep 2013 10:15
14 25.00 Walter Trump Nuremberg, Germany 22 Sep 2013 10:24
15 25.00 Aicke Hinrichs Jena, Germany 22 Sep 2013 10:27
16 25.00 Heiko Schwartz Augsburg, Germany 22 Sep 2013 10:31
17 25.00 Herbert Kociemba Darmstadt, Germany 22 Sep 2013 10:35
18 25.00 Nicolas Bonifas Paris, France 22 Sep 2013 11:12
19 25.00 Heinz Druckmüller Schwaz, Austria 22 Sep 2013 11:15
20 25.00 Roman Andreev Saint-Petersburg, Russia 22 Sep 2013 11:57
21 25.00 Klaus Nagel München, Germany 22 Sep 2013 13:15
22 25.00 Roland Postle Manchester, United Kingdom 22 Sep 2013 13:17
23 25.00 Vincent Ligneres Strasbourg, France 22 Sep 2013 13:28
24 25.00 Tom Sirgedas Okemos, Michigan, United States 22 Sep 2013 17:33
25 25.00 Richard Zapor Los Angeles, California, United States 22 Sep 2013 18:18
26 25.00 John Metcalf Boston, England, United Kingdom 22 Sep 2013 18:25
27 25.00 Jim Gillogly Long Beach, California, United States 22 Sep 2013 18:36
28 25.00 Matt Mahoney Melbourne, Florida, United States 22 Sep 2013 20:15
29 25.00 Jeroen van der Burg Leiden, Netherlands 22 Sep 2013 20:25
30 25.00 Fumi Yura Akihabara, Japan 22 Sep 2013 20:32
31 25.00 Michael Hürter Saarbrücken, Germany 22 Sep 2013 21:21
32 25.00 John Morris Simi Valley, California, United States 22 Sep 2013 21:32
33 25.00 Martin Piotte Montreal, Quebec, Canada 22 Sep 2013 21:42
34 25.00 Lars Nagel Mainz, Germany 22 Sep 2013 22:41

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.09.2013, 06:41 
Аватара пользователя


21/02/10
1594
Екатеринбург
Пока люди вводят известные результаты.
https://en.wikipedia.org/wiki/Sparse_ruler

Удастся ли кому то из участников улучшить известные результаты? Это будет сделать очень трудно. Это надо быть гением. Уверен среди участников конкурса гении есть, надо чтобы им повезло чуть чуть.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.09.2013, 11:13 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #766822 писал(а):
Удастся ли кому то из участников улучшить известные результаты?


Улучшить будет сложно но возможно. Если удастся улучшить тогда предположение Peter Luschny будет опровергнуто. Если не удастся тогда возможно мы сможем доказать это предположение.

Давайте делать ставки на то какое первое решение будет улучшено! По моим подсчётам некоторые решение будет легче улучшить чем другие, потому что они дальше от максимального количествa рёбр. Я делаю ставку на N=31.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.09.2013, 11:14 
Аватара пользователя


21/02/10
1594
Екатеринбург
42-й набравший 25 баллов.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.09.2013, 12:24 
Аватара пользователя


21/02/10
1594
Екатеринбург
Параллельное обсуждение темы.
http://e-science.ru/forum/index.php?sho ... 5&st=540&#

-- Пн сен 23, 2013 14:29:15 --

Цитата:
For clearness I state this 'conjecture':

In the set of optimal rulers with S segments where S>12
there exists at least one ruler of Wichmann type,
i. e. a ruler and integers r>0 and s>0 exist
such that the difference representation of the ruler has the form
1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r.


Первое что приходит в голову. Конструкция 1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r состоит из 6 групп чисел. Для больших N разумным будет найти подобную конструкцию в которой групп чисел больше шести.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение24.09.2013, 06:16 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #766892 писал(а):
Параллельное обсуждение темы. http://e-science.ru/forum/index.php?sho ... 5&st=540&#


Друзья, а вы не хотите всё в одном месте обсуждать (тут)? Просто не хочется читать сразу 3 разных форума...

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение24.09.2013, 12:39 


16/08/05
1146
Цитата:
1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r

Интересно, что патерн 1^r, r+1, (2r+1)^(r+1), (4r+3)^s, (2r+2)^r, 1^r тоже работает, только все максимумы на единичку меньше получаются.

-- Вт сен 24, 2013 14:49:51 --

Первая идея - надо пытаться восстановить новый патерн из известных решений, для которых текущий шаблон W(r,s) не действует. А именно:
Код:
12
{0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50}

13
{0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58}
{0, 1, 2, 6, 8, 17, 26, 35, 44, 47, 54, 57, 58}
{0, 1, 2, 8, 15, 16, 26, 36, 46, 49, 53, 55, 58}
{0, 1, 3, 6, 17, 20, 27, 35, 45, 49, 53, 57, 58}
{0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58}
{0, 1, 5, 8, 12, 21, 30, 39, 48, 53, 54, 56, 58}

14
{0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68}

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение24.09.2013, 14:13 
Аватара пользователя


21/02/10
1594
Екатеринбург
Сильно еще не лазил по ссылкам. Может кто даст ссылку на статью, где доказыватеся, что патерн
    1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r
дает все различные разности в заданном диапозоне.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение25.09.2013, 04:41 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dmd в сообщении #767266 писал(а):
Первая идея - надо пытаться восстановить новый патерн из известных решений, для которых текущий шаблон W(r,s) не действует


Согласен, надо искать новые патерны. Любую линейку можно записать как {a1^b1, a2^b2, ..., a_n^b_n}, где n количество блоков и a^b означает b раз повторить разницу a. Для удобства сократим а^1 = а. Запишем все эти патерны в этом виде:

Код:
12
A1: {0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50} = {1^3, 20, 5, 4^4, 3^2}

13
A2: {0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58} = {1^3, 24, 5, 4^5, 3^2}
D: {0, 1, 2, 6, 8, 17, 26, 35, 44, 47, 54, 57, 58} = {1^2, 4, 2, 9^4, 3, 7, 3, 1}
B1: {0, 1, 2, 8, 15, 16, 26, 36, 46, 49, 53, 55, 58} = {1^2, 6, 7, 1, 10^3, 3, 4, 2, 3}
C1: {0, 1, 3, 6, 17, 20, 27, 35, 45, 49, 53, 57, 58} = {1, 2, 3, 11, 3, 7, 8, 10, 4^3, 1}
C2: {0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58} = {1, 2, 3, 11, 7, 3, 11, 7, 4^3, 1} = {1, 2, {3, 11, 7}^2, 4^3, 1}
E: {0, 1, 5, 8, 12, 21, 30, 39, 48, 53, 54, 56, 58} = {1, 4, 3, 4, 9^4, 5, 1, 2^2}

14
B2: {0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68} = {1^2, 6, 7, 1, 10^4, 3, 4, 2, 3}


Тут A1 похоже на А2, B1 на B2 и C1 на C2. Я проверил все эти патерны, ничего нового не нашёл.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение25.09.2013, 06:21 
Аватара пользователя


21/02/10
1594
Екатеринбург
Цитата:
Everyone,

Given that this contest has evolved into the rather daunting effort of
disproving the Wichmann conjecture, I'm lifting the "no teams"
restriction.

Teams which finish in the top two positions will be awarded mulitple
instances of the appropriate prize, one for each team member (up to 3
members).

If any of you would like to double- or triple-up, please let me know.

Al


Собираем команды?! Больше трех не собираться!

-- Ср сен 25, 2013 08:24:51 --

Цитата:
C2: {0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58} = {1, 2, {3, 11, 7}^2, 4^3, 1}


Интересная конструкция. Надо ее покрутить.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение25.09.2013, 08:48 


16/08/05
1146
dimkadimon в сообщении #767590 писал(а):
Код:
12
A1: {0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50} = {1^3, 20, 5, 4^4, 3^2}

13
A2: {0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58} = {1^3, 24, 5, 4^5, 3^2}


Эти два набора сложились у меня в такой патерн
Код:
1:r,(r+1)(s+1):1,(r+2):1,(r+1):s,r:(r-1)
p=2r+s+2

Но.. Вариантов его модификации очень много. Можно :1 заменить на :(r-2), можно (r+2) заменить на (2r-1). Быть может логично трёх-параметрический патерн W(r,s,t) пытаться соорудить?

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение25.09.2013, 08:51 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Я проверял эти два набора так: W(r,s)={1:3, r, 5:1, 4:s, 3:2}

-- 25.09.2013, 14:58 --

Мы с Pavlovsky создали команду.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение25.09.2013, 10:34 
Аватара пользователя


21/02/10
1594
Екатеринбург
Дмитрий согласился стать капитаном команды.

Конкурс фактически превратился в коллективное опровержение Wichmann conjecture. Судя по всему, программировать придется немного. А вот исследовательская работа предстоит большая. Пожелайте нашей команде удачи. Ну и буду рад увидеть еще новые команды исследователей.

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

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



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

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


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

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