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

Диагностика для 10 класса. Код — упорядоченная строка: символы можно повторять, если они не стоят рядом. В отличие от набора предметов, перестановка знаков меняет код. Для алфавита из m символов и длины n ≥ 1 верно N = m·(m−1)ⁿ⁻¹: первый знак выбирается m способами, каждый следующий — m−1 способом. В этой карточке важно не просто получить число, но и объяснить, что ученик пересчитал дважды или ошибочно исключил допустимые варианты.

Например, для четырёх букв и трёх позиций правильное количество равно 4·3² = 36. Рассуждение «сначала поставим любую букву, затем вычтем повторы AA, BB, CC, DD» ненадёжно: в более длинных строках ограничения на разные пары соседей пересекаются. Одни и те же плохие строки могут вычитаться несколько раз.

Таблица ошибок: укажите причину и исправьте подсчёт

Проследите, как меняется множитель m−1. Он не связан с «запретом использовать букву повторно вообще». После последовательности ABA допустимо снова взять A: запрещено только равенство последней и новой буквы. Подсчёт «без повторений» m!/(m−n)! — другая модель.

Самостоятельные вопросы о повторном счёте

11. Для алфавита {0, 1, 2, 3} и длины 3 ученик разделил 36 на 3!, потому что «порядок несущественен». Почему это неверно?
12. Код длины 4 составляют из A, B, C, причём первая буква A. Ученик оставил 3 выбора на второй позиции. Исправьте число вариантов.
13. Из букв A, B, C, D составляют коды длины 4 без равных соседей и с первой буквой B. Ученик получил 4·3³. Где появился лишний множитель?
14. Из трёх знаков составляют строки длины 3, начинающиеся и заканчивающиеся A. Ученик получил 2². Проверьте последнюю позицию.
15. Сколько кодов длины 3 из {A, B, C} содержат A ровно на первой позиции и нигде далее? Объясните, почему результат не равен 3·2².
16. В алфавите из 4 букв строят код из 2 знаков. Ученик посчитал сначала 4·3, затем вычел ещё 4 кода вида AA. Объясните повторное исключение.

Ключ и исправление рассуждений

• 11. Неверно: ABC и CBA — разные строки, число допустимых кодов 36, а не 6.
• 12. Первый знак фиксирован, затем 2 выбора три раза: 2³=8. Буква A не может идти сразу после A.
• 13. Фиксированный первый B даёт 3³=27. Множитель 4 ошибочно считает четыре первых буквы.
• 14. Схема A ? A: средняя буква только B или C, последний A разрешён. 2 кода, а не 4.
• 15. Первая A, вторая B или C (2 выбора), третья — другая из B и C (1 выбор): 2 кода.
• 16. Формула 4·3 уже отбрасывает равные соседние буквы. Повторное вычитание четырёх AA, BB, CC, DD ошибочно; ответ 12.

Ещё одна распространённая ошибка — ошибочное применение принципа включений и исключений. Для строки длины 3 события «первая пара равна» и «вторая пара равна» пересекаются: AAA принадлежит обоим. Если вычитать числа строк с этими событиями, надо вернуть пересечение. Поэтому правило последовательного выбора обычно проще и безопаснее.

Проверка результата: при m=1 существует только один код длины 1; для любой длины n≥2 допустимых кодов нет. При m=2, n≥1 существует ровно два чередующихся кода. Это позволяет быстро обнаруживать невозможные формулы без больших вычислений. При фиксированном первом символе ответ (m−1)ⁿ⁻¹, но только когда фиксированный знак действительно входит в алфавит.

Разбор четырёх ловушек при проверке таблицы

Первая ловушка — путаница между ограничением «соседи различны» и ограничением «все знаки различны». При длине четыре из алфавита A, B, C допустимы ABAB, ACAC, ABCB и многие другие. Если исключить повторяющееся появление A вообще, такие коды потеряются. Но в условии нет запрета возвращаться к уже использованному символу после промежуточного другого знака. Проверить смысл можно по двум соседним клеткам любой строки, не сравнивая все её позиции одновременно.

Вторая ловушка — суммирование по вариантам первого символа с последующим повторным умножением на размер алфавита. Допустим, в условии первая позиция уже равна B. Тогда выбирать её снова нельзя: наборы кодов с первым A и первым B не пересекаются, но при фиксированном B нужен только один набор. Если первая буква не зафиксирована, таких равномощных наборов m, и только тогда появляется множитель m. Это различие особенно заметно в заданиях 12 и 13.

Третья ловушка связана с последней позицией. Когда она тоже задана, не всегда можно просто зафиксировать её после применения общей формулы. Например, в строке A?A промежуточный символ обязан отличаться от A, но завершающее A уже допустимо. А если записать A?B, последний B может совпасть со средней буквой, и это нужно исключить дополнительно. Поэтому при двух закреплённых концах следует перечислять возможные промежуточные знаки или использовать более подробную схему состояний.

Четвёртая ловушка — механическое применение деления на факториал. В комбинаторике такое деление возникает, когда один и тот же объект получается несколькими одинаково многочисленными способами его записи. У кодов с различными позициями перестановка знаков обычно меняет объект. Более того, различные коды могут иметь разное число перестановок из-за повторяющихся символов. Поэтому единый множитель «исправления» здесь не только не нужен, но и не обоснован.