нерешаемая задача

[nov]

Задачка уже с историей...Лет 7-8 назад, при подготовке заданий к турниру матбоёв, использовал несколько своих задач (составляю иногда...). Но в одной из них мое решение оказалось неверным, и до сего момента не найдено (хотя задачку видели и решали немало моих знакомых). А теперь, собственно, главное...Есть N камней, каждый весом не более 1кг, и весы. Из этих камней выбирают часть(может быть и все, но по крайнее мере один) и раскладывают на чаши весов таким образом, чтобы разность весов d имела наименьшую возможную абсолютную величину для данного набора. Какое наибольшее значение может принимать d по всем таким наборам камней (при фиксированном N).
P.S. Для N=3 d=1/4, при наборе камней 1/4, 1/2, 1кг.(это легко). Но уже при N=4 я долго считал d=1/8, что неверно. . А в общем случае - нет и предположений...Надеюсь, задачка понравится...

[Lyoha]

nov в сообщении #267382 писал(а):

Для N=3 d=1/4, при наборе камней 1/4, 1/2, 1кг.(это легко).

А мне почему-то кажется, что d=1. (это легко).

nov в сообщении #267382 писал(а):

Но уже при N=4 я долго считал d=1/8, что неверно.

Не считал, но тоже 1. Для любого N.

nov в сообщении #267382 писал(а):

Надеюсь, задачка понравится.

Совсем не понравится. Либо я не понял условие и в чём здесь прикол, либо одно из двух.

[venco]

Lyoha, не обязательно все камни класть на весы.

[worm2]

Действительно, интересная задача.
Похоже, d(1/4)=1/7: {3/7, 5/7, 6/7, 7/7}.
Возможно, задача допускает такую переформулировку: для заданного N найти минимальное D (=1/d), что существует такое множество $N_D$ из N натуральных чисел, не превышающих D, что суммы чисел любых двух различных подмножеств $N_D$ различаются.

[gris]

nov просто почему-то сказал - "по крайней мере один" и запутал. Один камень нельзя разложить по чашкам. Я так понял, что ищется минимум разности двух сумм по всем непересекающимся непустым подмножествам каждого множества из $n$ положительных чисел, не больших единицы и требуется найти наибольшее значение минимума уже по всем множествам.
Ведь так?

PS То есть, всё же разность может равняться весу одного камня?

[worm2]

Я так понял, что сначала из исходного множества камней берётся подмножество (непустое), а потом уже это подмножество разбивается всевозможными способами ещё на 2 подмножества (оно из них может быть и пустым, т.е. мы можем положить на одну чашу один камень, а на другую --- не положить ничего).

У меня получилось N(5)>=1/12: {6/12,7/12,9/12,11/12,12/12} (склоняюсь к тому, что равенство строгое).

[venco]

worm2 в сообщении #267558 писал(а):

У меня получилось N(5)>=1/12: {6/12,7/12,9/12,11/12,12/12} (склоняюсь к тому, что равенство строгое).

6+12 = 7+11.

-- Ср дек 02, 2009 13:05:23 --

N(5) = 13: { 3, 6, 11, 12, 13 }/13
N(6) = 24: { 11, 17, 20, 22, 23, 24 }/24
N(7) = 44: { 20, 31, 37, 40, 42, 43, 44 }/44

[venco]

The On-Line Encyclopedia of Integer Sequences даёт несколько вариантов продолжения:
http://www.research.att.com/~njas/sequences/index.html?q=1%2C2%2C4%2C7%2C13%2C24%2C44
Мне больше нравится вот эта: http://www.research.att.com/~njas/sequences/A006744

[Pavlovsky]

A sum packing problem of Erdos
http://www.research.att.com/~njas/sequences/A005318

http://www.research.att.com/~njas/sequences/A096858
{1}
{1,2}
{2,3,4}
{3,5,6,7}
{6,9,11,12,13}
{11,17,20,22,23,24}
{20,31,37,40,42,43,44}
{40,60,71,77,80,82,83,84}
{77,117,137,148,154,157,159,160,161}
{148,225,265,285,296,302,305,307,308,309}
{285,433,510,550,570,581,587,590,592,593,594}
{570,855,1003,1080,1120,1140,1151,1157,1160,1162,1163,1164}
{1120,1690,1975,2123,2200,2240,2260,2271,2277,2280,2282,2283,2284}
{2200,3320,3890,4175,4323,4400,4440,4460,4471,4477,4480,4482,4483,4484}
{4323,6523,7643,8213,8498,8646,8723,8763,8783,8794,8800,8803,8805,8806,8807}