Подсчёт числа допустимых расположений для кодов без соседних одинаковых знаков: тренажёр для 10 класса

Математика, 10 класс. Исследование цифровых и символьных кодов: важны именно соседние символы, а не уникальность всех знаков.

Наблюдение: почему нельзя считать как перестановку без повторений

Придумайте код длины 4 из букв А, Б, В. Последовательность АБАБ допустима: повторяющиеся А не стоят рядом. ААБВ недопустима из-за первых двух позиций. Значит, правило «все знаки различны» было бы слишком строгим.

Сформулируй правило и проверь контрпример

Для алфавита из q символов и длины L ≥ 1 число строк без равных соседей равно q·(q − 1)^{L − 1}. Если первый символ уже фиксирован, начальный множитель q исчезает. Для цифрового кода, начинающегося ненулевой цифрой, при разрешённом алфавите 0,…,q−1 первая позиция имеет q−1 вариант. Условия для каждой позиции проверяют по соседу слева, а не по всем ранним знакам.

Контрпример к неверному правилу «каждый знак использовать только один раз»: при двух символах и длине 5 допустимы АБАБА и БАБАБ. Наивное произведение 2·1·0… дало бы ноль, что неверно.

Исследовательский тренажёр: 14 разных условий

1. Три разные буквы, длина 4; повторы несоседних букв разрешены.
2. Четыре значка, длина 5; соседние значки обязаны отличаться.
3. Два символа, длина 7; одинаковые рядом запрещены.
4. Пять букв, длина 3; код может повторять первую букву в конце.
5. Четыре буквы, длина 4; первая буква заранее задана А.
6. Три знака, длина 6; первый знак уже выбран и закреплён.
7. Четырёхзначный цифровой код из цифр 0–9; первая цифра не 0.

Дополнительные случаи: фиксированный знак, ноль и нарушения

8. Три цвета для пяти позиций, одинаковые соседние цвета недопустимы.
9. Пять символов, длина 4; начало фиксировано знаком ♣.
10. Двоичный код длины 9 без соседних совпадений.
11. Три клетки заполняют четырьмя значками: соседние разные.
12. Цифры 0–5, длина 5, начало не ноль, соседние цифры разные.
13. Три буквы, длина 4; найдите число кодов с хотя бы одним одинаковым соседством.
14. Четыре значка, длина 3; сколько кодов нарушают правило разных соседей?

Почему подсчёт по позициям действительно работает

Рассуждение удобно представить деревом выбора. Из первой вершины выходят q ветвей, соответствующих первой букве. Из каждой такой ветви выходят q − 1 продолжений: нельзя выбирать только букву, которая была непосредственно слева. Сколько бы одинаковых букв ни встретилось раньше, предыдущих позиций мы не проверяем. Поэтому число ветвей на каждом следующем шаге одно и то же. Это позволяет умножить количества вариантов вместо полного перебора.

Пусть алфавит состоит из А, Б и В, а код имеет длину три. У первой позиции три варианта, у второй — два, у третьей — тоже два. Получаем 12 строк. Для начала А они таковы: АБА, АБВ, АВА, АВБ. По четыре строки начинаются с Б и с В. Обратите внимание, что АБА — разрешённый код, хотя в нём два раза встретилась буква А. ААВ — запрещённый, хотя в нём всего две различные буквы.

Что происходит с границами и нулём

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

Двоичный алфавит — показательный крайний случай: после 0 обязательно идёт 1, а после 1 обязательно 0. Значит, для любой положительной длины существуют только две строки без равных соседей. Их можно выписать полностью: чередование с 0 и чередование с 1. Это согласуется с формулой 2·1^L−1=2. Если в алфавите всего один символ, то при длине больше единицы допустимых строк вообще нет.

Счёт через дополнение без двойного вычитания

Условия «все соседние различаются» и «есть хотя бы одна пара равных соседей» образуют два непересекающихся случая, которые вместе покрывают все возможные строки. Например, из трёх знаков строятся строки длины четыре: всего 3⁴=81, хороших 3·2³=24, а нарушающих правило 57. Не пытайтесь вычесть отдельно строку с равными знаками на первых позициях, потом на вторых и так далее: строки АААБ и АААА встретятся в нескольких группах. Вычитание дополнения учитывает каждую ровно один раз.

Практическая самопроверка модели

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

Подробный ключ

1. Разбор: 3·(3 − 1)³ = 24. Последний символ может совпасть с первым, если между ними есть другая позиция.
2. Разбор: 4·(4 − 1)⁴ = 324. Последний символ может совпасть с первым, если между ними есть другая позиция.
3. Разбор: 2·(2 − 1)⁶ = 2. Последний символ может совпасть с первым, если между ними есть другая позиция.
4. Разбор: 5·(5 − 1)² = 80. Последний символ может совпасть с первым, если между ними есть другая позиция.
5. Разбор: Первый знак уже выбран; для остальных 3 позиций по 3 возможностей: 3³ = 27.
6. Разбор: Первый знак уже выбран; для остальных 5 позиций по 2 возможностей: 2⁵ = 32.
7. Разбор: Для первой позиции 9 ненулевых знаков, для каждой следующей — 9 знаков, отличных от предыдущего: 9⁴ = 6 561.
8. Разбор: 3·(3 − 1)⁴ = 48. Последний символ может совпасть с первым, если между ними есть другая позиция.
9. Разбор: Первый знак уже выбран; для остальных 3 позиций по 4 возможностей: 4³ = 64.
10. Разбор: 2·(2 − 1)⁸ = 2. Последний символ может совпасть с первым, если между ними есть другая позиция.
11. Разбор: 4·(4 − 1)² = 36. Последний символ может совпасть с первым, если между ними есть другая позиция.
12. Разбор: Для первой позиции 5 ненулевых знаков, для каждой следующей — 5 знаков, отличных от предыдущего: 5⁵ = 3 125.
13. Разбор: Всего 3⁴ = 81 последовательностей; без соседних повторов 24. Нарушающих хотя бы одно соседство: 57 (дополнение, а не вычитание по каждой паре отдельно).
14. Разбор: Всего 4³ = 64 последовательностей; без соседних повторов 36. Нарушающих хотя бы одно соседство: 28 (дополнение, а не вычитание по каждой паре отдельно).

Для задания с «хотя бы одним» равным соседством удобнее взять дополнение: все коды минус хорошие. Это учитывает коды, у которых две и более пары одинаковых соседей, ровно один раз. Считать такие пары по отдельности и складывать нельзя: один код попадёт в несколько групп.

Контроль понимания

Объясните, чем отличается запрет повтора на соседних позициях от запрета повтора вообще. Приведите пример допустимого кода с повтором несоседних знаков. Отдельно поясните, почему закреплённый первый знак уменьшает число вариантов в q раз, а ограничение «не начинать с нуля» — не всегда в q раз.

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