Разделы 
Дополнительно
Задача по математике - 8
2015-02-14 
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов,
но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.
Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, ÐБВШГÐБ - слово, а ÐБВ,Ш, ШГÐБ - его подслова.
Решение:
Ð ассмотрим последовательность слов:
Ð, ÐБÐ, ÐБÐВÐБÐ, ÐБÐВÐБÐГÐБÐВÐБÐ, ...
Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз.
Докажем методом полной индукции следующее утверждение: в n-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых n букв алфавита, то такие подслова появятся. Тогда
33-е слово является требуемым (в русском алфавите 33 буквы).
База индукции. Для n=1 утверждение очевидно.
Шан индукции Пусть утверждение справедливо для всех слов с номерами от 1 до n−1. Ð ассмотрим n-е
слово. В нем n-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с (n−1)-м словом.
Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в (n−1)-м слове. Значит, одно из них содержит n-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в n-м слове тоже нет соседних одинаковых подслов.
Если приписать к n-му слову n-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером k
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов,
но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.
Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, ÐБВШГÐБ - слово, а ÐБВ,Ш, ШГÐБ - его подслова.
Решение:
Ð ассмотрим последовательность слов:
Ð, ÐБÐ, ÐБÐВÐБÐ, ÐБÐВÐБÐГÐБÐВÐБÐ, ...
Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз.
Докажем методом полной индукции следующее утверждение: в n-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых n букв алфавита, то такие подслова появятся. Тогда
33-е слово является требуемым (в русском алфавите 33 буквы).
База индукции. Для n=1 утверждение очевидно.
Шан индукции Пусть утверждение справедливо для всех слов с номерами от 1 до n−1. Ð ассмотрим n-е
слово. В нем n-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с (n−1)-м словом.
Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в (n−1)-м слове. Значит, одно из них содержит n-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в n-м слове тоже нет соседних одинаковых подслов.
Если приписать к n-му слову n-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером k
