Завершая (ну, почти) тему выборов из списков с условиями, давайте я вернусь к
задаче о Кощее, Иване-дураке и волшебной дудочке — и вообще к последовательностям с запретами.
Эту часть мне рассказал Алексей Куликов — спасибо ему за ссылки и комментарии!
Помните, я когда-то
упоминал последовательность Морса-Туэ, явно предъявляемую последовательность 0 и 1, в которой нет тройных повторов (и даже подслов вида aXaXa). Её можно построить бесконечным применением к начальному слову w_1=0 бесконечной череды замен
0->01, 1->10,
а ещё она получается, если каждый индекс n записать в двоичной системе, а потом сложить «цифры» по модулю 2. Получается слово
w=0110100110010110…
Если цифр есть хотя бы три — то есть слова, в которых никакое подслово не повторяется подряд даже дважды (нет никаких подслов вида XX). И такие слова тоже впервые построил Аксель Туэ — вот тут можно посмотреть переводы его работ, и на с. 11 есть утверждение:
Theorem 2.1 (Satz 3). There exist arbitrarily long square-free words over three letters.Итак, если рассматривать слова из k символов 1,2,…,k и запрет на повтор подслов — то уже при k=3 такое бесконечное слово есть. Вы ведь уже догадались, что будет дальше?
Вопрос. Пусть для каждого n задан список A_n из хотя бы k символов. Обязательно ли существует бесконечное слово w=(w_n), такое, что:
- каждый символ w_n выбирается из соответствующего списка A_n, и
- w не содержит квадратов, т. е. подслов вида XX?
Конечно, очень хочется сказать, что когда символы различные, не иметь повторений проще… Только вот мы уже знаем, что для «списочной» задачи четырёх красок не просто из этого не получается сделать строгое рассуждение, а даже ответ
другой, нужно 5 красок в списке!
Для k=4 ответ на вопрос выше положительный — и совсем недавний! Его сначала получили в статье
A new approach to nonrepetitive sequences Jarosław Grytczuk, Jakub Kozik, Piotr Micek (
препринт 2011 года,
статья).
Они использовали такое рассуждение: будем каждый раз дописывать случайную букву (из списка для текущего номера), а потом, если вдруг на конце появился повтор XX, второе повторённое X сотрём. Оказывается, тогда рано или поздно мы напишем сколь угодно длинное слово без повторов.
Потому что — давайте сделаем большое число M шагов такого процесса и будем, как шахматисты, вести протокол, записывая в него:
* на каждом шаге — то, как меняется текущая длина слова (она может возрасти на 1 или уменьшиться на длину вычеркнутого слова |X|).
* и в конце — «финальную позицию», какое слово в итоге получилось.
Несложно понять, что по такому протоколу можно восстановить обратным ходом и всю «партию»: если нам удавалось добавить букву, то от текущего слова нужно последнюю стереть, а если нет, то мы знаем, слово X какой длины было вычеркнуто, так что мы сначала повторяем последние |X| букв, возвращая вычеркнутое X на место, а потом стираем последнюю (дописанную на этом шаге) букву.
Так вот — оказывается, что если строящееся слово не может оказаться длиннее n символов, то при достаточно большом числе шагов M нам не хватит протоколов. Потому что всех партий 4^M, финальных позиций вообще ограниченное количество, а количество путей, по которым изменяется длина слова, можно оценить через ~числа Каталана как o(4^M). Точнее — давайте записывать изменение длины как последовательность из M символов « +1 » (когда пытаемся дописать букву) и почти M символов « -1 » (в количестве |X| там, где вычёркивается слово X). Эта последовательность длины не больше 2M, и все её частичные суммы остаются между 0 и n, так что легко поверить, что такие последовательности составляют (на самом деле, даже экспоненциально) малую долю от всех
2^{2M+1} -1 = 2*4^M -1
последовательностей из +1 и -1 длины не больше 2M.
Вот и получается, что игр всего 4^M, а протоколов o(4^M). При том, что по протоколу ход игры однозначно восстанавливается. Противоречие.
МА 
