Задача 78300

Темы:    [ Последовательности (прочее) ] [ Процессы и операции ]

Сложность: 5 Классы: 10,11

Условие

Даны 2ⁿ конечных последовательностей из нулей и единиц, причём ни одна из них не является началом никакой другой. Доказать, что сумма длин этих последовательностей не меньше n ^. 2ⁿ.

Решение

Набор последовательностей, удовлетворяющий условиям задачи, мы назовём "правильным". Пусть дан правильный набор, состоящий из 2ⁿ последовательностей. Последовательности длины строго меньше n (если такие в наборе имеются) мы будем называть "короткими", в отличие от "длинных" — длины больше n и "полных" — длины ровно n. Покажем прежде всего, что если правильный набор, состоящий из 2ⁿ последовательностей, содержит короткие последовательности, то он непременно содержит и длинные последовательности. Допустим, что существует набор, не содержащий ни одной длинной последовательности, но содержащий хотя бы одну короткую. Составим по этому набору новый правильный набор по следующему правилу. Все полные последовательности перенесём в новый набор без изменений, а все короткие последовательности допишем всеми возможными способами до полных и все полученные последовательности включим в новый набор. Правильность такого набора очевидна. Новый набор состоит только из полных последовательностей, и потому в нём не больше, чем 2ⁿ, последовательностей (ибо существует ровно 2ⁿ последовательностей длины n, состоящих из 0 и 1). С другой стороны, новый набор содержит больше последовательностей, чем исходный, так как каждая короткая последовательность порождает не меньше двух полных. Это, однако, противоречит тому, что в исходном наборе было 2ⁿ последовательностей. Если теперь в наборе нет коротких последовательностей, то нам нечего доказывать. Остается предположить, что данный правильный набор из 2ⁿ последовательностей содержит длинные, короткие и, возможно, полные последовательности. Построим тогда по данному набору новый правильный набор следующим образом. Возьмём самую длинную последовательность (если их несколько, то любую) и зачеркнём в ней последний знак. Если при этом набор остался правильным, то поступим с этим набором точно так же, и т. д., пока при некотором вычёркивании новый набор — обозначим его через N — не станет неправильным. Последнее произойдёт в том случае, когда укороченная на один знак последовательность совпадёт с некоторой другой или станет её началом. Совпадение, однако, невозможно, так как в этом случае уже шаг назад набор был неправилен: вторая последовательность была началом первой (неукороченной). Итак, в наборе N некоторая последовательность является началом некоторой другой последовательности . При этом лишь на один знак длиннее , так как до укорачивания последовательность была самой длинной. Поскольку существует лишь две последовательности требуемой длины с началом : 0 и 1, то, кроме , в наборе N не может быть другой последовательности, для которой была бы началом (так как она имела бы своим началом или , или неукороченную последовательность ). Вычеркнем теперь из набора N последовательность , тогда набор станет правильным. Кроме того, возьмём любую короткую последовательность , вычеркнем её и добавим в набор две последовательности: и . Правильность нового набора также очевидна. Посмотрим, как менялась при этих преобразованиях сумма длин всех последовательностей набора. При вычёркивании последнего знака у длинной последовательности сумма, очевидно, уменьшалась. При вычёркивании длинной последовательности теряется не меньше, чем n + 1 знак, а при добавлении вместо короткой последовательности d, длина которой не больше n - 1, двух последовательностей и приобретается не больше, чем (n - 1) + 2 = n + 1 знак. Таким образом, и в этом случае сумма длин всех последовательностей не увеличивается. Общее число последовательностей в наборе неизменно: оно равно 2ⁿ. В результате описанных преобразований мы придём к правильному набору из 2ⁿ последовательностей, в котором не будет больше длинных последовательностей. Но, по доказанному выше, такой набор не содержит также и коротких последовательностей, т. е. состоит из 2ⁿ последовательностей длины n. Сумма длин исходного набора оказывается, таким образом, не меньше, чем n ^. 2ⁿ, что и требуется.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	25
Год	1962
вариант
	1
Класс	9
Тур	2
задача
Номер	5