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

[spamsink]

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

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

Comments

[lj_frank_bot]

Hello!
LiveJournal categorization system detected that your entry belongs to the category: Дети.
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[sevabashirov]

Максимально возможный набор - 955, а всего наборов - 1023.

ДИРИХЛЕ! ДИРИХЛЕ!!! (с) А. Савватеев

[palindromer]

Если надо использовать все 10 чисел, то есть разложить их на две кучки с одинаковой суммой, а сами числа произвольные, то так можно сделать не в любом случае. Например набор 1,2,3,4,5,6,7,8,9,99 не получится разделить на две равных суммы.

[spamsink]

В условии нигде не сказано, что нужно использовать все 10 чисел.

И я добавил в условие куда-то девшееся слово "целых", спасибо.

[aafin]

"Из них составить" как бы намекает на то, что из них всех. Лучше "выбрать из них два набора" или типа того

[spamsink]

КМК, как бы намекало, на то, что из них всех, если бы было сказано "разделить на два набора". Впрочем, в любом случае очевидно, что раз сумма всех 10 чисел может быть и нечётной, то такое понимание условия неверно.

[avva]

Может, стоит пояснить, что не все 10 чисел обязаны входить в два набора.

Решение вытекает сразу из 2^10 > 10*100.

[spamsink]

И еще из принципа Дирихле. :) Кстати, хороший вопрос, "очевиден" ли он, и если да, то начиная с какого возраста (или, если угодно, вплоть до какого возраста).

[alexanderr]

внутри Земли находится другой шар, размером гораздо больше наружного

[xxxxx]

Ну 2 в степени 10 чуть больше чем 10х100, всё-то у вас, программистов, вокруг килобайтов вертится