Al Zimmermann - Sums and Products

[Pavlovsky]

https://en.wikipedia.org/wiki/Sidon_sequence
Sidon sequence

Цитата:

All finite Sidon sets are Golomb rulers

Про линейки совсем недавно был конкурс.

-- Вт дек 01, 2015 10:42:57 --

https://en.wikipedia.org/wiki/Golomb_ruler
Golomb ruler

[dimkadimon]

Pavlovsky
Ну вот вы фактически испортили всем соревнование... теперь вы можете догнать Jarek.

[Pavlovsky]

Это открытый источник. Вообще то там только суммы. А ведь надо еще произведение. Алгоритм Эрдёша на первый взгляд слабоват. Готовые результаты только до N=27.

[whitefox]

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

Ну вот вы фактически испортили всем соревнование

Какое странное заявление.
Лично у меня "подсказки" Pavlovsky всегда только увеличивали интерес к конкурсу. И на моей памяти только один человек был этим недоволен. Вот теперь появился второй.

[Pavlovsky]

A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS
http://eeme.ucd.ie/~kdrakaka/work/publi ... Rulers.pdf

Это весьма интересно.

-- Вт дек 01, 2015 13:17:01 --

Поиск по "Golomb ruler Methods of construction" дает кучу ссылок. Глаза разбегаются, не знаю с чего начать.

[whitefox]

Pavlovsky
Спасибо, это действительно весьма интересно.

[dimkadimon]

whitefox в сообщении #1078513 писал(а):

Какое странное заявление.
Лично у меня "подсказки" Pavlovsky всегда только увеличивали интерес к конкурсу. И на моей памяти только один человек был этим недоволен. Вот теперь появился второй.

Обычно я не против подсказок, но на этот раз подсказка настолько сильная что конкретно меняет ситуацию и если честно даже портит конкурс. На данный момент только 7-8 человек на конкурсе обнаружили связь между линейками Голомба и задачей. Подсказку можно было сделать менее очевидной, например "Если в решение все суммы различны то и все разницы различны тоже". Я не сильно сержусь на Pavlovsky, он часто высказывает очень умные и полезные идеи сам этого не осозновая. Часто его подсказки мне помогали найти хорошие результаты и только увеличивали интерес к конкурсу. Тут возможно ситуация будет немного другая, так как найти хорошие линейки Голомба достаточно сложно и подозреваю большинство будут использовать уже известные результаты. Тогда у всех будут те же решения и это скучно. Конечно есть шанс что мы сможем найти новые линейки и это будет очень интересно.

[Pavlovsky]

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

На данный момент только 7-8 человек на конкурсе обнаружили связь между линейками Голомба и задачей.

Ой. Я взял книгу "Unsolved problems" (ссылку на нее давал dimkadimon). Нашел задачу C9. Запустил поиск по "Sidon sequence". Нашел статью в википедии. Оттуда вышел на линейки Голомба.

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

Просто много людей, не успев дочитать задание до конца, начинают кодить первое что пришло им в голову.

Забавно, в каком классе школы ученик сможет сообразить, что $a-b=c-d$ и $a+d=c+b$ одно и тоже?

[whitefox]

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

На данный момент только 7-8 человек на конкурсе обнаружили связь между линейками Голомба и задачей.

Странно, имхо, эта связь очевидна. И тем более странно, что вы, как автор задачи, умолчали об этой связи.

[Pavlovsky]

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

на этот раз подсказка настолько сильная что конкретно меняет ситуацию и если честно даже портит конкурс. На данный момент только 7-8 человек на конкурсе обнаружили связь между линейками Голомба и задачей.

Без вашей рекламы, мой пост может никто бы и не заметил. Так что если завтра люди массово начнут выкладывать решения на основе линеек Голомба, в этом будет и ваша заслуга.

Конечно у меня есть идеи как использовать линейки Голомба, для решения текущей задачи. Но после ваших слов я сильно задумался, может я пропустил очень сильные идеи?!

[dimkadimon]

whitefox в сообщении #1078553 писал(а):

Странно, имхо, эта связь очевидна. И тем более странно, что вы, как автор задачи, умолчали об этой связи.

Кому очевидна, а кому нет. 90% людей не нашли эту связь...

Автор задачи Ал, это его идея. Я просто проверил сложность этого варианта и он мне показался сложнее остальных. Не понимаю почему автор должен указывать связь? Ал принимает такие решения.

[Herbert Kociemba]

dimkadimon: When I first read your comment about Pavlovsky spoiling the contest I really thougth that you meant this ironically.

Because the connection to Golomb rulers for the "+" part is obvious. And I think it is obious too that you can try to get solutions from this which also satisfy the "*"-part by adding an offset to the sequence.
For N=11 I took for example a cyclic difference set (CDS) with some offset to get a solution near to the optimum without any programming.
http://www.inference.phy.cam.ac.uk/cds/part3.htm and the following pages are quite interesting to read in this context.

[Pavlovsky]

Может кто подскажет. Что это такое и как его вычислить?
g a primitive root of F(p).

F(p) конечное поле, p простое число.

[whitefox]

Это примитивный элемент поля $\mathbb{F}_q,$ при $q$ простом равен первообразному корню по модулю $q.$

-- 01 дек 2015, 15:59 --

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

Не понимаю почему автор должен указывать связь?

Если автор сам участник (а я полагал, что автор — вы), то такое поведение не спортивно.

[Pavlovsky]

Изучаю статью A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS

Понравился алгоритм (Теорема 5)

Цитата:

These rulers are asymptotically optimal

Правда алгоритм слишком заумный.

Цитата:

it is necessary to construct $F(q^3)$

Интересно, реально ли построить такое конечное поле для N=5003?