Раскрываем скобки комбинаторными рассуждениями

Заметим, что в задаче по сути спрашивается, какие степени мы можем получить, после раскрытия всех скобок. Рассмотрим для начала первые скобок. Докажем, что после их перемножения появятся степени от 0 до Ясно, что степень, а также степень мы можем получить. Пусть мы может получить степень тогда пусть для получения этой степени мы из скобок взяли степени Если то существует или свободная степень Тогда мы точно сможем получить Понятно, что степень, большую получить невозможно. Теперь вспомним про оставшиеся скобок. Пусть из первых скобок мы получили тогда из оставшихся мы можем получить степеней: Так как то для каждой степени, полученной после перемножения первых скобок, будет порождаться новая серия степенй после перемножения оставшихся скобок. Действительно, каждый показатель из дает свой уникальный остаток при делении на Тогда ответ