Набор последовательностей, удовлетворяющий условиям задачи, мы назовём "правильным".

Пусть дан правильный набор, состоящий из 2ⁿпоследовательностей. Последовательности длины строго меньшеn(если такие в наборе имеются) мы будем называть "короткими", в отличие от "длинных" — длины большеnи "полных" — длины ровноn. Покажем прежде всего, что если правильный набор, состоящий из 2ⁿпоследовательностей, содержит короткие последовательности, то он непременно содержит и длинные последовательности. Допустим, что существует набор, не содержащий ни одной длинной последовательности, но содержащий хотя бы одну короткую. Составим по этому набору новый правильный набор по следующему правилу. Все полные последовательности перенесём в новый набор без изменений, а все короткие последовательности допишемвсеми возможными способамидо полных и все полученные последовательности включим в новый набор. Правильность такого набора очевидна.

Новый набор состоит только из полных последовательностей, и потому в нём не больше, чем 2ⁿ, последовательностей (ибо существует ровно 2ⁿпоследовательностей длиныn, состоящих из 0 и 1). С другой стороны, новый набор содержит больше последовательностей, чем исходный, так как каждая короткая последовательность порождает не меньше двух полных. Это, однако, противоречит тому, что в исходном наборе было 2ⁿпоследовательностей.

Если теперь в наборе нет коротких последовательностей, то нам нечего доказывать. Остается предположить, что данный правильный набор из 2ⁿпоследовательностей содержит длинные, короткие и, возможно, полные последовательности.

Построим тогда по данному набору новый правильный набор следующим образом. Возьмём самую длинную последовательность (если их несколько, то любую) и зачеркнём в ней последний знак. Если при этом набор остался правильным, то поступим с этим набором точно так же, и т. д., пока при некотором вычёркивании новый набор — обозначим его черезN— не станет неправильным. Последнее произойдёт в том случае, когда укороченная на один знак последовательность совпадёт с некоторой другой или станет её началом. Совпадение, однако, невозможно, так как в этом случае уже шаг назад набор был неправилен: вторая последовательность была началом первой (неукороченной).

Итак, в набореNнекоторая последовательность$\bar{a}$является началом некоторой другой последовательности$\bar{b}$. При этом$\bar{b}$лишь на один знак длиннее$\bar{a}$, так как до укорачивания последовательность$\bar{a}$была самой длинной.

Поскольку существует лишь две последовательности требуемой длины с началом$\bar{a}$:$\bar{a}$0 и$\bar{а}$1, то, кроме$\bar{b}$, в набореNне может быть другой последовательности, для которой$\bar{a}$была бы началом (так как она имела бы своим началом или$\bar{b}$, или неукороченную последовательность$\bar{а}$).

Вычеркнем теперь из набораNпоследовательность$\bar{b}$, тогда набор станет правильным. Кроме того, возьмём любую короткую последовательность$\bar{d}$, вычеркнем её и добавим в набор две последовательности:$\overline{d0}$и$\overline{d1}$. Правильность нового набора также очевидна.

Посмотрим, как менялась при этих преобразованиях сумма длин всех последовательностей набора. При вычёркивании последнего знака у длинной последовательности сумма, очевидно, уменьшалась. При вычёркивании длинной последовательности$\bar{b}$теряетсяне меньше, чемn+ 1 знак, а при добавлении вместо короткой последовательностиd, длина которой не большеn- 1, двух последовательностей$\overline{d0}$и$\overline{d1}$приобретаетсяне больше, чем(n- 1) + 2 =n+ 1 знак. Таким образом, и в этом случае сумма длин всех последовательностей не увеличивается. Общее число последовательностей в наборе неизменно: оно равно 2ⁿ.

В результате описанных преобразований мы придём к правильному набору из 2ⁿпоследовательностей, в котором не будет больше длинных последовательностей. Но, по доказанному выше, такой набор не содержит также и коротких последовательностей, т. е. состоит из 2ⁿпоследовательностей длиныn. Сумма длин исходного набора оказывается, таким образом, не меньше, чемn ^. 2ⁿ, что и требуется.

Ответ задачи отсутствует