Простенькая задачка

[spamsink]

Бывший сослуживец-американец, ныне живущий в Неваде, на прошлой неделе посещал наши края, и на нашей с ним встрече-прогулке задал задачку:

Даны 10 различных целых чисел в диапазоне от 1 до 100. Докажите, что из них можно составить два различных набора с одинаковой суммой. (Возможно, в девичестве это какая-то старая русскоязычная детская задачка с

Comments

[serge_gris]

2^10-2 > 900

[morfizm]

Наборов 2^10 = 1024 (сумма у пустого набора = 0?), а сумма лежит в диапазоне от 0 до... в худшем случае это 100+99+98+...+91 = 90*10 + 55 = 955.

По принципу Дирихле, разные суммы будут только у 956 наборов. Мы обломимся либо на 957-ом, либо раньше.

[xaxam]

Не знал такую хорошенькую задачу. 1024=2^10 > 10*100=1000 и привет от Дирихле.

Но формулировка действительно требует внимательности: первые несколько секунд я думал над возможностью разложить гирьки на две равновесные кучки.

[spamsink]

Кстати говоря, существует пример набора из 8 чисел, дающих уникальные суммы (99 98 96 92 88 80 68 44, проверено электроникой), а вот насчет 9 я не уверен ни в одну из сторон.

Похоже, что среди 9 чисел всегда найдутся два набора с одинаковой суммой, но я не вижу, как бы это можно было легко доказать или опровергнуть.

[xxxxx]

про гирьки было похожее, но не совсем это у пользователя old_greeb - «Дано натуральное М. Для какого наибольшего натурального N можно найти M гирек, таких чтобы с их помощью можно было взвесить любой груз с целочисленным весом в диапазоне от 1 до N на весах с двумя чашками (то есть где и в плюс и в минус грузики идут)». Там ответ чуток неожиданный для любителей компьютерных наук.

[old_greeb]

Если знать способ, ответ, кажется, очевидный?

[pharmazevt]

Потому что количество возможных различных наборов больше, чем количество возможных сумм?

[sevabashirov]

В условии все же есть место для двойной трактовки - могут ли быть наборы пересекающимися. Если нет, то это уже другая задача.

[spamsink]

Какая разница? Если оказывается, что есть два разных пересекающихся набора с одинаковой суммой, то очевидно, что если исключить из них общую часть, то будет два непересекающихся набора с одинаковой суммой.

[sevabashirov]

Точно!