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

[spamsink]

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

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

Comments

[relf]

Принцип Дирихле. Различных неаустых наборов 2^10-1=1023, а сумма в каждом не превышает 10*100=1000. Ну а из двух наборов с одинаковой суммой, выкидывая общие элементы, можно получить два непересекающихся набора с одинаковой суммой.

[caztd]

(2**10)-2=1022 разных наборов (subsets), максимально возможная сумма <1000 (955?), значит есть разные наборы с одинаковой суммой.

[dolovar]

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

Попробуем составить набор без повторений:
1,
2, а вот 3 уже нельзя потому что 1+2,
4, 1+4, 2+4, 1+2+4,
8, 1+8, 2+8, 1+2+8, 4+8, 1+4+8, 2+4+8, 1+2+4+8,
16, 1+16, 2+16, 1+2+16, 4+16, 1+4+16, 2+4+16, 1+2+4+16, 8+16, 1+8+16, 2+8+16, 1+2+8+16, 4+8+16, 1+4+8+16, 2+4+8+16, 1+2+4+8+16,
32...
64... 4+32+64

До 128 не дойдем, потому что условие до 100.
Семи бит достаточно для чисел до сотни включительно.
Какое целое число меньше 101 ни прибавь к набору из семи чисел [1,2,4,8,16,32,64], получится возможность составить одно из уже существующих в наборе, что противоречит условию.

[spamsink]

Это решает какую-то другую задачу. Нужно доказать, что найдутся два набора с одинаковой суммой при любых исходных 10 числах.

[dolovar]

Если набор может состоять из одного числа, то решена данная задача.
Сумма чисел в первом наборе сможет равняться числу во втором наборе при любых (различных) исходных 10 (даже 8) числах до 100 включительно.

[spamsink]

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

[sunch]

Интересно было бы понять, каким образом дети, знающие арифметические действия и значение слова "докажите", должны дойти до формулы 2^n (в предположении что до 955 и Дирихле таки дойдут).

[spamsink]

Эксперименты с количеством разных непустых поднаборов из множеств меньшей мощности дадут, например, 2, 6, 14, где можно увидеть, что разности увеличиваются вдвое. Проверив это на множестве из 5 элементов (это ещё вполне доступно вручную) и убедившись, что действительно получается 30, несложно будет досчитать до 1022 для 10 элементов, не вдаваясь в степенную зависимость.

[sunch]

То есть, фактически, придумать индукцию. Хотел бы я посмотреть на ребенка, который сразу после арифметических действий и значения слова "докажите" способен на такое. Терренс Тао наверное смог бы (говорят, он в два года уже что-то из математики объяснял соседям по песочнице).

[yakov_sirotkin]

А что будет, если потребовать в условии 2 непересекающихся набора?

[spamsink]

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