У меня в кармане ровно 26 монет достоинством 1,2, ..., 26 лавэ.
Какое наибольшее число монет я могу взять из кармана так, чтобы среди взятых мною монет нельзя было выбрать две кучки с одинаковой суммой?

P.S. "выбрать две кучки" и "разложить на две кучки" не одно и то же.

(25) я не про программу, а про базовые знания.

(38) ну и какие тут базовые знания можно применить?

(39) =) если бы я знал, ну или хотя бы помнил) я бы не спрашивал

Могу доказать что можно выбрать не более 8 монет,
У 9 монет 511 сочетаний, а сумма максимальная 351

(39) видимо что-то из теории множеств

(41) 511 различных сочитаний? или большенство из уникальных намного меньше?

4 8 18 23 24 26

(43) 511 уникальных сочетаний

4 8 18 23 24 25

(44)8+18=26

26,1,3,22,16,14,9,

(48) нет опть :(

1+3+22=26

22 1
14 9

вариантов из 6 много, больше не получиться, только как это доказать

(41) разверни тему

(53) в смысле?

(54) не вкуриваю

(55) 9 моент, каждую можем либо взять либо нет. Вариантов 2^9, но не взять ни одной монеты из девяти не можем. Итого 511

(56) это понятно

что то типа: берем 1 число, остальные на 1,2,4,8,16 больше или меньше его. получаем разные варианты из 6. да?

У нас 511 сочетаний, а вариантов суммы 371, соответсвенно из девяти монет всегда можно подобрать одинаковую сумму двумя способами.

(59) как посчитал варианты суммы?

(60) максимальная сумма - 1+2...+26=371, минимальная 1, сколько целых чисел в этом интервале?

(61) йопаный стыд, пора в отпуск, спасибо

(62) это мне пора в отпуск, хотя я и так в нем :)
Максимальная сумма с девяти монет значительно меньше
26 25 24 23 22 ...18

198, так что могу доказать что и восьмью монетами не собрать.

хотя непонятно, мы ведь из 9 монет должны взять две кучки, значит либо берем в первую кучку, либо во вторую, либо не берем - причем кучки 1 и 2 между собой не различаются

3 9 11 13 15 21 23 - итого 7 - верно?

Шесть монет вариант предложен, нужно или найти вариант с семью, либо доказать что это невозможно.

(65) а нет

(65) ты же сам написал что не разложить на две кучки.

(66)нет

(69) да там все верно, просто ты ухудшаешь оценку, но все равно получается, что 8 нельзя

(66) 3 9 11

7 можно, после доказательства, что 8 нельзя неинтересно подбирать
выкладывать или нет?

Надо доказать что 7 нельзя.

(73) тьфу, семь нельзя ))

(70) а ну да. ошибся. без 23
3 9 11 13 15 21

(73) нет, подожди.

6 можно, продолжаем улучшать ситуацию

11+13 = 9+15

(0) зачем такое в пятницу ? -)

(79) 34=24?

(81) все пора домой :( ужас

4 11 16 20 23 25 26

(83) 4+16=20

(83) 4+16=20 см (36)

любые 25 монет можно взять

(86) и не возвращать ))

(85) под суммой понимается общая сумма кучки, или непременно сумма как сложение как минимум двух? или я что-то не так понял?

(88) достаю из кармана сколько то монет, пытаюсь собрать из них 2 кучки с равной суммой, все использовать необязательно

(89) (4 16) и (20) - это не 2 кучки с равной суммой?

(89) > все использовать необязательно

Тогда конечно не (86)

Все, пас, не могу 7 в уме подобрать.

(92) надо доказать, что их нет

(90) да, две, с равной суммой

что-то интересно стало. теперь ночь спать не буду, интересует логическое решение =)

(92) проверь
9 14 19 22 24 25 26

нет увы :(

на самом деле для метода NS максимальная сумма для кучки из N элементов, это сумма N-1 элемента (ведь кучка не может быть одна)
поэтому для 7 макс. сумма равна (26+21)*6/2=141

(96)24+9=14+19
нельзя 7.

100

(98) не понял. Что значит одна?

максимум 2 монеты

Ибо если взять 3 монеты достоинством 1,2,3, то их можно разбить на 2 кучки в 1 кучке монеты 1 и 2 в итоге дающие 3, во второй кучке одна монета = 3.

если мы берем любое количество большее 3 монет, то из них набираем 2 кучки как описано выше.

Тогда уж сумма шести элементов +1, за кучку из всех семи.

Сумма пяти элементов + 7 (сочетаний семи элементов) +1(сочетаний семи элементов)

Итого 118, а сочетаний 127, и понятно что раз сочетаний больше, то какая то сумма собирается больше чем одним способом.

Сумма пяти элементов, максимум 110 + 7 сочетаний шести +1 сочетание семи.

(103) не понял

(107) кучка может состоять из одной монеты, двух и т.д.
Если в кучке <=5 монет, то вариантов суммы не больше чем максимальная сумма 26+25+24+23+22=110
Если в кучке шесть монет, то вариантов суммы не больше чем возможных разных кучек (7)
Если в кучке семь монет, то вариант такой кучки всего один. То есть и возможная сумма только одна.

Я неправильно сложил арифметическую прогрессию :)

(108) кучки из 7 монет не существует, иначе что ты положишь во вторую кучку?

(110) посмотри еще раз свое условие. Монеты в кучках могут пересекаться.

(111) не могут, иначе делаем полное пересечение и оп-ля

"выбрать две кучки" = выбрать два непересекающихся подмножества
"разложить на две кучки" = выбрать два непересекающихся подмножества, что их объединение дает все вытащенное множество

(113) где в условии про непересекающиеся?

Разбить тогда нужно писать. А ты написал выбрать.

(114) да хрен с ним, о чем спор, пусть пересекаются, убираем из каждой пересечение, получаем все равно равные суммы

(115) разбить это когда каждая монета попадает в одну из кучек

(116) одна может быть подмножеством другой.

+(116) все равно кучки из 7 монет при всего 7 монетах быть не может

(118) ага и суммы их равны, ну да

(117) а выбрать - то одна монета может быть в обеих. Сначала сделал одну выборку, поом опять монеты в кучу, потом другую.

(119) это почему же я все монеты не могу положить в кучу?

(120)
Три монеты всего
1,2
1,2,4
Суммы равны?

(122) читай (120) к (118)

(123) конечно нет

(124) но я же все монеты положил в кучу.

Если разбить, то доказывается легко, а если две выборки - то пока ещеине доказал.

(126) в одну все, а в другую?

(128) а в другую любое сочетание, но не все.

(129) и суммы заведомо не равны, смысл какой?

(130) я уже ничего не соображаю...

(131) а у меня через 10 минут отпуск ))

(130) у меня третий день уже. Вчера еще и тепловой удар получил.

1,2,4
Вариантов суммы - 7
Сочетаний семь.
Чтоб гарантированно нельзя было разбить надо чтоб число сочетаний, с учетом выбора всего множества было больше чем возможных сумм.

Доказательство.
С четырех и меньше значений мы максимум можем набрать 98 + сочетаний пяти 21 + сочетаний шести 7 и одно сочетание семи. То есть всего 127 разных сумм.
Но если мы должны набирать все значения 1,2,3...16 то у нас должно быть не менее четырех чисел меньше 16. То есть 98 мы с четырех не наберем, так как меьшее среди них не 22, а заметно меньше.

(0)(135) А так? 1 4 10 18 23 25

Нет ли у задачи связи с wiki:Линейка_Голомба ?

(136) вариант из шести в веткеиуже есть.
А у тебя
1 4 18
23