Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео
Ошибка.
Попробуйте повторить позже
Палиндром — это слово, которое не меняется, если в нём переставить буквы в обратном порядке, например 
. Сколько
различных 
-буквенных слов можно составить из букв 
так, чтобы они не содержали палиндромов длины больше
Источники:
Подсказка 1
Что означает, что у нас есть палиндром? Это значит, что есть палиндром чётной длины или нечётной длины. А что следует из этого утверждения? Какое более просто условие на слово нам достаточно проверять, чтобы слово было свободно от палидромов?
Подсказка 2
Это значит, что не должно быть палиндрома длины 2 и длины 3. Ну отсутствие палиндрома длины 3, равносильно тому, что у нас буквы через 1 не совпадают. А отсутствие длины два, значит, что не совпадают соседние. Какое тогда условие равносильно отсутствию палиндромов длины 2 и 3?
Подсказка 3
Эти условия равносильны тому, что среди трёх подряд идущих букв нет совпадающих! Тогда остается простейшая комбинаторная задача на подсчёт количества вариантов!
Заметим, что две центральные буквы любого палиндрома чётной длины одинаковы, то есть образуют палиндром длины два. Точно так же
три центральные буквы палиндрома нечётной длины образуют палиндромы длины три. Таким образом, отсутствие в слове палиндромов
равносильно отсутствию палиндромов длины 
и 
Это, в свою очередь, равносильно тому, что любые три подряд идущие буквы в слове
различны.
Первая буква в слове выбирается пятью способами, для следующей остаётся 
способа. Каждая из последующих букв не может
совпадать с двумя предыдущими, поэтому для неё остаётся 
способа. Все эти числа надо перемножить, поэтому мы
получаем
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
