Al Zimmermann - Sums and Products

[dimkadimon]

Можно поинтересоваться, сколько у вас максимумов?

[Gassa]

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

Только текущих максимумов. Конечно рано радоваться.

Уф, это хорошо :) . Я уж испугался, что задача прямо совсем решена.

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

Можно поинтересоваться, сколько у вас максимумов?

Я посылал сразу пачкой, так что теперь уже не узнать.

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

[dimkadimon]

Gassa в сообщении #1074473 писал(а):

Уф, это хорошо :) . Я уж испугался, что задача прямо совсем решена.

Задача фактически решена - посмотрите на очки в топ 10. Остались может 2-3 улучшения. Узор настолько очевидный...

[dimkadimon]

Нашел первые теоретические результаты для этой задачи:

http://www.plouffe.fr/simon/math/Unsolv ... %20Guy.pdf (глава F18, стр 138)
https://www.renyi.hu/~p_erdos/1976-36.pdf (глава 23, стр 19-20)
http://renyi.hu/~p_erdos/1983-18.pdf

Очень приятно знать что эту задачу решал (и не решил) такой великий человек как Эрдёш. Кстати, он рассматривал более общий случай когда можно использовать несколько цифр, например: $a_i+a_j+a_k,a_i*a_j*a_k$. Если окажется что даная задача слишком простая то предлагаю продолжать соревнование с общим вариантом.

[Pavlovsky]

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

Очень приятно знать что эту задачу решал (и не решил) такой великий человек как Эрдёш.

Очередная задача с большой историей. Даже 300 человек за 3 месяца не в состоянии решить задачу с большой историей.

[dimkadimon]

Pavlovsky в сообщении #1074506 писал(а):

Очередная задача с большой историей. Даже 300 человек за 3 месяца не в состоянии решить задачу с большой историей

Зависит что вы имеете ввиду под "решить"? Решить для общего $N$ может и не смогут, а вот для конкретных $N$ вполне возможно.

[Pavlovsky]

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

Зависит что вы имеете ввиду под "решить"?

Обычно конкурсы с такими задачами заканчиваются большим количеством набранных 25 баллов. Люди просто пользуются известными достижениями в решении задачи. Продвинуть решение задачи вперед не удается никому.

-- Ср ноя 18, 2015 11:30:50 --

Запустил поиск "size of the set of sums and products of a set".

Ничего нового со времен Эрдёша.

[whitefox]

Pavlovsky в сообщении #1074506 писал(а):

Даже 300 человек за 3 месяца не в состоянии решить задачу с большой историей.

Особенно если они старательно избегают сотрудничества.

[whitefox]

Кстати, Эрдёш ссылается на книгу Freiman G.A. Foundations of a structural theory of set addition как на источник своих идей. Это английский перевод книги Фрейман Г.А. Начала структурной теории сложения множеств (кликнуть 11661). Может кому пригодится.

[Pavlovsky]

Первые 25 баллов есть. Полагаю, что это не улучшаемый оптимум. Тем самым призовые места уже разыграны. У скольких участников будет 25 в конце конкурса?

[whitefox]

Al Zimmermann писал(а):

The contest is 4 days old. Each of the best solutions has been found by several people, and two people have found all of them. IMHO, this does not make for an interesting contest.

I'm willing to change the rules. Suggestions welcome.

Al

Задача решена?

[Pavlovsky]

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

Задача решена?

Эрдёш занимался нижней оценкой задачи. Работ по верхней оценке не видел.

[whitefox]

Посмотрите Теорему 1 из третей ссылки dimkadimon

[Pavlovsky]

Опс, не внимательно посмотрел.

Конкурс практически закончен, значит можно более свободно обсуждать идеи!

[whitefox]

dimkadimon
Вау, похоже Вы будете третьим.