Иванов Андрей Владимирович:
По-моему ответ Гаряка Асмик верен.
Единственный способ выполнить условие 3 в общем случае - это раздать всем детям подарок одного типа. Выполнение условия 2 достигается перебором всех подмножеств из n - 1 типа подарков, количество вариантов таких подмножеств есть 2^n-1.
Решение несколько несправедливо в том смысле, что кому-то дадут только один подарок, а кому-то - все n штук. Но в задаче не сказано, что у детей должно быть одинаковое число подарков.

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

Иванов Андрей Владимирович:
ОК, пойдем по методу математической индукции. Для 2 типов подарков очевидно, что формула верна. Пусть она верна для n. Детей 2^n-1 и это максимум. То есть добавить к этому комплекту нечего. Для n+1 - новый тип подарков построим множество из предыдущего так: 2ⁿ тот же комплект и еще 2ⁿ с добавлением нового вида подарка. Можно ли увеличить это число? Нет, так как это будет отсутствовавший в множестве для n либо такой же, но с подарком нового типа. В любом случае конфликт с условием 3.

>> Гаряка Асмик

Хорошо. Спасибо. Надеюсь, что такой ответ прокатит (задача из д/р).

Гаряка Асмик:
Здравствуйте.

Вы в обоих вариантах предлагаете конкретный способ построения множества комплектов подарков. Таким образом Вы показываете, что можно раздать 2^n-1 комплектов подарков, но никоим образом не отметается возможность построения множества большей размерности.