Индукция в комбинаторике

Пример. Рассмотрим множество всех двоичных последовательностей длины у которых последние разрядов фиксированы как нули, а первые разрядов произвольны. Размер множества: Для любой последовательности изменение любого из первых 20 разрядов даёт другую последовательность из множества. Таким образом, каждая последовательность имеет ровно 20 соседей, отличающихся ровно в одном разряде.

Оценка. Докажем более сильное утверждение: если в множестве последовательностей (длины ) из нулей и единиц у каждого элемента есть хотя бы других, отличающихся от него ровно в одном разряде, то содержит хотя бы элементов.

Доказательство проведём индукцией по

База: Если у каждой последовательности есть хотя бы один сосед, то

Пусть утверждение верно для Рассмотрим множество где у каждой последовательности есть хотя бы соседей. Возьмём произвольный разряд (например, первый) и разделим на:

Для любой последовательности

• Среди её соседей не более одного отличается в первом разряде
• Если такой сосед существует, он лежит в другом подмножестве
• Остальные соседи отличаются в других разрядах и лежат в том же подмножестве

Таким образом, в своём подмножестве или последовательность имеет не менее соседей.

По предположению индукции: и Следовательно:

Для получаем Пример показывает, что оценка достижима.