В языке Лориков словом считается последовательность из десяти (русских) букв, содержащая фрагмент "КОТ", а в языке Ёриков словом считается последовательность из одиннадцати (русских) букв, содержащая фрагмент "МЫШЬ". Маленькую Верочку спросили, в каком из этих двух языков содержится больше слов. Но Верочка умеет считать только до одиннадцати. Как ей ответить на данный вопрос, не прибегая к полному перебору?
Ответы
Ответ: в языке Ёриков больше слов, чем в языке Лориков.
Решение:
Сначала заметим, что в языке Лориков фрагмент "КОТ" может стоять в семи разных позициях [первая буква фрагмента - первая буква слова, вторая буква слова, третья буква, и так далее до седьмой буквы]. Так что все разнообразие языка Лориков заключается в семи оставшихся буквах (и различных позициях фрагмента). Если Верочка узнает, сколько разных слов (любых, но из русских букв) можно составить в виде последовательности из семи русских букв (любых) и умножит получившееся число на на 7 (число размещения фрагментов "КОТ" в слове), то она узнает общее количество слов в языке Лориков (это только ее мысли, пока она не должна проводить никаких арифметических операций и подсчет слов из семи букв).
В языке Ёриков постоянный фрагмент("МЫШЬ") может стоять тоже на семи различных позициях. Различаются только семь оставшихся букв (и положения фрагмента в слове). Получается, что Верочке достаточно подсчитать количество различных слов виде последовательности из семи русских букв (абсолютно любых) и умножить на семь (опять же: пока Верочка ничего не должна считать!).
Теперь Верочка сравнивает то, что ей нужно подсчитать:
Язык Лориков: количество слов-комбинаций из семи букв * 7.
Язык Ёриков: количество слов-комбинаций из семи букв * 7.
Теперь Верочка обнаруживает, что и там, и там одно и то же.
Но также некоторые слова были подсчитаны несколько раз, например: "КОТКОТАААА", "МЫШЬМЫШЬААА". Теперь нужно сравнить количество таких слов. В языке Лориков кроме двух "КОТов" останется еще 10 - 3 - 3 = 4 свободных мест. Для Ёриков останется (два повторяющихся фрагментов) 11-4-4 = 3. Во-первых, 4>3, уже в языке Лориков больше повторов, еще можно добавить третьего "КОТа", тогда количество повторяющихся комбинаций возрастет.
Получается, что в языке Ёриков слов больше (Верочка подсчитала меньше повторов).