Ах, комбинаторика! Эта загадочная наука, которая заставляет старшеклассников терять сон и верить, что формулы — это не просто набор символов, а тайные заклинания из Гарри Поттера. Я — учитель информатики с 2003 года (да-да, я видел больше экзаменов, чем у вас было выходных), и скажу вам по секрету: комбинаторика — это настоящий клад лёгких баллов.
Главное — понять её на уровне смыслов, а не просто зубрить формулы как стихи наизусть.
Представьте себе: перестановки — это когда у вас есть куча разных игрушек, и вы хотите узнать, сколько способов их расставить в ряд. Тут порядок важен!
Если у вас n игрушек — то вариантов n! (читается как «эн факториал», и звучит почти как заклинание).
А если вы берёте только часть из них и тоже считаете порядок — вот тогда это размещения. И наконец сочетания — когда порядок уже не играет роли, как если бы вы выбирали друзей для команды без очередности.
Но что делать, если повторения разрешены? Тогда мы переходим в цифровой мир систем счисления. Помните старый анекдот: «Почему программисты любят шестнадцатеричную систему?
Потому что 10 шестнадцатеричных – это 16 десятичных!» Вот примерно так и с повторениями: начинаешь считать по своим правилам и понимаешь, что мир гораздо шире привычных десяти цифр.
Ну а теперь представьте себе лексикографический порядок – это словно алфавитный марафон слов. У нас есть буквы А, К, О, Р, С и Т (в русском алфавитном порядке), из которых составлены все пятибуквенные слова. Вот начало списка: ААААА – первое слово; ААААК – второе; дальше идут всё новые комбинации. Задача звучит так: найти последнее слово с чётным номером в списке (то есть под номером 2, 4, 6 и так далее), которое не начинается на А, С или Т и содержит ровно две буквы О.
Звучит страшно?
Не бойтесь! Представьте себе такую ситуацию: вы — библиотекарь в огромной библиотеке слов. Вам поручили найти книгу с очень странным названием по очень строгим критериям.
Вы берёте каждую книгу по порядку (в нашем случае слово) и проверяете условия. Лексикографический порядок можно представить как число в шестеричной системе счисления (где А=0, К=1 и так далее). Таким образом каждое слово превращается в число от 0 до 6^5-1.
Проверив варианты методом перебора (ну или с помощью магии математики), мы выяснили: искомое слово соответствует числу 5057 в этой системе (помним про N+1). В буквенном виде оно выглядит как «РТООТ».
И да — оно действительно не начинается с запрещённых букв и содержит ровно две буквы О!
Теперь переключимся на другую задачу — посчитать количество пятиричных семеричных чисел длины пять с ровно одной цифрой шесть и без подряд одинаковых цифр. Если вы подумали «что?» — не переживайте!
Это как готовить блюдо по сложному рецепту: сначала ставим главную звезду – цифру шесть – на первую позицию. Остальные позиции заполняем цифрами от нуля до пяти так, чтобы ни одна цифра не стояла рядом со своей копией (ведь никто не любит скучные повторы).
Если первая цифра шесть – вариантов получается 750 (звучит аппетитно!). Если же первая цифра не шесть или ноль (ведущий ноль запрещён!), то единственная шестерка может стоять на любой из оставшихся четырёх позиций. Для каждого варианта подсчитываем количество подходящих чисел отдельно – снова получаем по 750 вариантов для каждой позиции шестерки.
В итоге сумма всех случаев – целых 3750 уникальных чисел!
Представьте себе толпу таких чисел на вечеринке без соседних двойников-шестерок.