головоломка про последовательности

vitamin8808

Существует ли такая бесконечная последовательность из нулей и единиц, в которой никакое слово не повторяется два раза подряд? Слово — любая конечная последовательность длины больше 1.
Никто не знает красивого решения?

vitamin8808

ответ: таких последовательностей нет.
Я решал так: сначала тупым перебором (не очень долго) показывается, что последовательность, начинающаяся с "000" подыхает, ну а дальше уже просто. Смотрим всё хорошие слова длины 5, и что дальше может получится. В несколько строк получаем, что они все дохнут.

griz_a

А подряд это по окончанию одного другое или со смещением на один символ.
В смысле в 0001 00 два раза подряд или нет?

vitamin8808

В смысле в 0001 00 два раза подряд или нет?
Нет. Совсем подряд, "словослово".

griz_a

Ну я переборчик нашел, не знаю, особо ли красивый.
Отойдем от начала слова символов на 5.
Начиная с этого места ищем 0 между двух 1.
101
После этого не 0, перед этим не 0
Значит 11011
После этого не 0, перед этим не 0
1110111
Ну и еще один виток приводит к 1111, что недоступно.
Отсюда нет 0 и 1 отдельными блоками.
Рассмотрим блок 00 в единицах
110011
после этого блока идет не 11, не 00, не 01 (иначе одинокий нолик)
Значит 11001110
перед ним - не 10, не 11, не 00. Значит 01
0111001110
Перед 0 тоже 0, чтобы не было голых 0, значит повтор 00111
Выходит, что двухсимвольных блоков тоже нет.
Значит все трехсимвольные и подряд одинаковые они идти не могут.
Очевиден повтор

vitamin8808

Да, важно заметить, что "101" и "010" не могут встречаться (в глубине так перебор упрощается сильно.
Тогда нули и единицы идут только блоками 00, 000, 11, 111.
Значит 01
0111001110
Уже повтор, 01110 — 01110 :D
Cпасибо, думаю, что легче решения уже нет.
Оставить комментарий
Имя или ник:
Комментарий: