Условие
Найдите число двоичных строк длины 8, в которых ровно три единицы и никакие две единицы не соседствуют.
Решение по шагам
Пусть места единиц a₁<a₂<a₃. Запрет соседства означает a₂≥a₁+2 и a₃≥a₂+2. Уберите обязательные промежутки: b₁=a₁, b₂=a₂−1, b₃=a₃−2. Тогда 1≤b₁<b₂<b₃≤6.
Получилось взаимно однозначное соответствие с выбором трёх позиций из шести, поэтому ответ C(6,3)=20. Обратное преобразование добавляет промежутки и гарантирует отсутствие соседних единиц.
Проверка результата
Перебор всех 2⁸=256 строк с двумя фильтрами — сумма цифр равна 3 и нет подстроки 11 — находит 20. Обратное преобразование для каждого выбора восстанавливает одну строку.
Типичная ошибка
C(8,3) учитывает соседние единицы. Нельзя независимо выбирать места для каждой единицы: порядок и обязательные зазоры связывают позиции.
Что даёт этот метод
Для строки длины n с k несоседними единицами ответ C(n−k+1,k), если n≥2k−1. Доказательство даёт и простой алгоритм генерации.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.