Высшая проба 2015 и ранее

Подсказка 1

Разберёмся отдельно с произведением (1+х)...(1+х^14). Из каждой скобки (1+х^i) мы берём либо 1, либо x^i. Тогда какие степени при раскрытие скобок мы можем получить?

Подсказка 2

Все суммы, где числа от 1 до 14 либо не участвуют, либо участвуют один раз. То есть эти степени лежат в промежутке [0,14+...+1] = [0, 105]. А все ли суммы можно получить из этого диапазона?

Подсказка 3

Оказывается, да... Доказать в общем виде... Хм. Ну не, звучит страшно. А если по порядку? Например, сначала для 0, потом для 1. А потом для остальных?...

Подсказка 4:

Верно! Намёк на индукцию. Придумайте переход самостоятельно (он несложный)). А на что мы ещё не обращали внимания? Мы забыли про скобку (1+x^1000)^18.

Подсказка 5:

По биному Ньютона это сумма x^(1000k), где k = 0,1,2,...,18, со страшными коэффициентами (C-шки). То есть степени из первых 14 скобок это числа из множества А = 0, …, 105 а из последней в 18 степени это числа из множества B = 0, 1000, …, 18000. Тогда какой вывод можно сделать?

Подсказка 6:

Что степени x в итоговом выражении — это всевозможные суммы одного числа из А и другого из B. Дальше остаётся совсем немного (понять, что случаи не пересекаются) Вы справитесь! Успехов!