Восстановление числа вариантов для кодов без соседних одинаковых знаков — карточки с ответами, 10 класс

Исследовательский урок: 10 класс. Сколько кодов длины n можно составить из m знаков, если одинаковые знаки не могут стоять рядом? Сначала исследуем не просто готовый результат, а способ получить количество шаг за шагом. Пусть T(n) — число корректных кодов длины n. Первый знак свободен, последующий должен отличаться от предыдущего; поэтому T(1)=m, T(n+1)=(m−1)T(n), значит T(n)=m(m−1)ⁿ⁻¹. Здесь порядок позиций важен, а одинаковый знак можно вернуть спустя одну позицию.

Наблюдение и собственная гипотеза

Сделайте вывод самостоятельно: при увеличении длины на единицу число вариантов умножается не на m, а на m−1. Контрпример к утверждению «все символы различны»: при двух знаках 0 и 1 код 01010 допустим, хотя знаки повторяются. Недопустим только соседний повтор. Для m=1 формула даёт T(1)=1 и T(n)=0 при n≥2.

Задания: восстановите количество либо неизвестное условие

1. Для алфавита из 5 символов найдите количество корректных кодов длины 4.
2. Коды длины 6 строят из двух символов 0 и 1. Сколько их всего? Перечислите оба.
3. При m=4 и n=5 сколько кодов начинаются заранее заданной буквой R?
4. Для алфавита из трёх символов найдите T(6) и отношение T(6)/T(5).
5. Известно: T(2)=30. Сколько символов в алфавите? Основание m — целое ≥2.
6. Коды составляют из четырёх знаков. При какой длине n количество кодов равно 108?
7. Из пяти символов создают коды длины 3. Сколько строк начинаются не с буквы A?
8. Для трёхсимвольного алфавита длина 4. Сколько кодов начинаются и заканчиваются символом A?
9. Бинарный код длины 8 должен начинаться с 1. Сколько допустимых строк?
10. Коды из 4 знаков длины 4: сколько из них заканчиваются заранее указанным символом Q?
11. Из пяти знаков составляют трёхзначные коды, где первая позиция фиксирована как P. Найдите общее число и объясните, почему его нельзя делить на 3!.
12. Известно T(3)=12 и символов не меньше двух. Найдите m.
13. Из пяти символов составляют коды длины 3. Сколько начинаются A и заканчиваются также A?
14. Из алфавита {A,B,C} составляют коды длины 4. Сколько кодов содержат только буквы A и B (буква C не используется)?

Подробный ключ с основаниями решений

• 1. 5·4³=320.
• 2. 2 кода: 010101 и 101010; новые знаки всегда вынужденно чередуются.
• 3. 3⁴=81; для первого символа выбора нет.
• 4. T(6)=3·2⁵=96, отношение равно 2.
• 5. m(m−1)=30 ⇒ m²−m−30=0 ⇒ (m−6)(m+5)=0; m=6. Отрицательное значение невозможно.
• 6. 4·3ⁿ⁻¹=108 ⇒ 3ⁿ⁻¹=27=3³, значит n=4.
• 7. Первый знак выбирают из четырёх (кроме A), затем 4 и ещё 4: 64.
• 8. При начале и конце A: A _ _ A. Для второй позиции 2 выбора. Для третьей из двух допустимых относительно второй букв подходит только та, что не A; итого 2, а не 6.
• 9. 1 строка — 10101010.
• 10. По симметрии каждый из четырёх символов встречается последним одинаково часто: T(4)/4=4·3³/4=27.
• 11. Первый P фиксирован: 4²=16 кодов. Перестановки знаков меняют позиции; делить на 3! нельзя.
• 12. m(m−1)²=12 ⇒ m=3 (3·4=12; при m≥2 выражение строго возрастает).
• 13. Схема A ? A: на среднюю позицию допускается любой из четырёх остальных символов. Ответ 4.
• 14. Два доступных символа должны чередоваться, поэтому 2 кода: ABAB и BABA.

При обратных задачах число знаков m не может быть дробным: символы алфавита перечисляются поштучно. В уравнении m(m−1)=30 отрицательный корень отбрасываем, а в задаче о длине T(n)=108 показатель n−1 должен быть неотрицательным целым. Такая проверка области допустимых значений необходима не меньше, чем вычисление самой степени.

Попробуйте доказать рекуррентное правило иначе: любой корректный код длины n можно продлить ровно m−1 способами — каким бы ни был последний символ, новый должен отличаться только от него. Ни один из полученных кодов длины n+1 не возникает из двух разных предыдущих кодов: его первые n знаков однозначно определены. Значит, пересечений нет и умножение действительно законно.

Удобная проверка для небольшого n — выписать строки. При m=3, n=2 имеем AB, AC, BA, BC, CA, CB, всего шесть. Это подтверждает T(2)=3·2. Обратите внимание: в примерах с фиксированными первой и последней позициями нельзя всегда применять обычную степень без уточнения последнего перехода: конечная буква также обязана отличаться от предпоследней.

Переход от наблюдения к доказательству

Начните с реального перечисления для m=3. При длине один это A, B, C; при длине два к каждой букве можно дописать любую из двух других. Получается шесть кодов. Если каждый из шести снова продолжить одним неравным последнему знаком, выходит двенадцать кодов длины три. Никакая строка длины три не попадает в счёт дважды, потому что по её первым двум буквам однозначно видно, из какого кода длины два она получена. Это и есть необходимое обоснование умножения на m−1.

Далее рассмотрите, почему ограничение касается пары соседних позиций, а не количества использований знака за весь код. В алфавите {0,1,2} строка 020202 допускается: каждое следующее значение отличается от предыдущего, хотя символы повторяются трижды. Строка 021122 не допускается: на границе третьей и четвёртой позиций стоят две единицы, а на последних позициях две двойки. Одного запрещённого соседства достаточно, чтобы исключить весь код.

Обратные задачи на m требуют целочисленной проверки. Например, если количество двухзначных кодов равно 30, получаем квадратное уравнение m²−m−30=0. У него два корня, но отрицательное число не может быть мощностью алфавита. Поэтому правильное значение m=6 единственное. Если количество кодов задано для другой длины, полезно сначала проверить соседние целые значения m, а затем доказать единственность по росту функции m(m−1)ⁿ⁻¹ при m≥2.

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

Проверка формул на маленьких примерах помогает увидеть это различие. Для трёх знаков и кода длины четыре с концами A и A нужно построить схему A ? ? A. Средняя пара должна начинаться с B или C, а завершаться другой из этих двух букв; получается ровно ABCA и ACBA. Для кода A ? ? B вариантов будет больше, поскольку третья буква может быть A либо C в зависимости от второй. Обычная формула T(n) описывает свободные концы, поэтому к фиксированным граничным условиям её нужно применять осторожно.

Наконец, параметры m и n имеют разные смыслы. Увеличение количества знаков расширяет выбор уже для первой позиции, тогда как увеличение длины добавляет переход с множителем m−1. При m=2 каждый новый переход имеет единственный вариант, поэтому длинных кодов не больше, чем коротких. Это не парадокс: запрет полностью определяет продолжение после выбора первого символа. Для m≥3 количество кодов растёт экспоненциально вместе с длиной.

Если у вас получился ответ, противоречащий таблице, перепроверьте самый первый шаг. Для алфавита из пяти символов код длины четыре имеет пять вариантов первого знака и затем три перехода по четыре варианта. Следовательно, общее число равно 320, а не 5·4⁴=1280: последняя запись содержит лишний переход, которого нет в строке. Этот способ проверки через количество границ между соседними позициями работает при любой длине: у n позиций ровно n−1 таких границ.

Чтобы самостоятельно провести исследование, измените одно условие и посмотрите, что произойдёт с формулой. Если начало кода зафиксировано, первая позиция больше не даёт множителя m. Если запрещено использовать какой-либо знак вообще, фактически уменьшается размер алфавита. Если вместо запрета одинаковых соседей требуется, чтобы все символы были попарно различными, выборы последовательно сокращаются от m до m−n+1, а при n>m решений вовсе нет. Это три разные математические модели, и ни одну нельзя подменять другой.