|
AvovA
|
|
cool russian dude
|
|
|
|
|
|
|
Рег.: 06.11.2002
|
|
Сообщений: 2425
|
|
Из: Toronto, Canada
|
|
Рейтинг: 447
|
|
головоломка про последовательности
17.01.2010 23:38
|
|
|
Существует ли такая бесконечная последовательность из нулей и единиц, в которой никакое слово не повторяется два раза подряд? Слово - любая конечная последовательность длины больше 1.
Никто не знает красивого решения?
|
пишите письма  |
|
|
AvovA
|
|
cool russian dude
|
|
|
|
|
|
|
Рег.: 06.11.2002
|
|
Сообщений: 2425
|
|
Из: Toronto, Canada
|
|
Рейтинг: 447
|
|
Re: головоломка про последовательности
[re: AvovA]
17.01.2010 23:41
|
|
|
ответ: таких последовательностей нет.
Я решал так: сначала тупым перебором (не очень долго) показывается, что последовательность, начинающаяся с "000" подыхает, ну а дальше уже просто. Смотрим все хорошие слова длины 5, и что дальше может получится. В несколько строк получаем, что они все дохнут.
|
пишите письма |
|
|
FrauSoboleva
|
|
Don't Quixote
|
|
|
|
|
|
|
Рег.: 20.11.2004
|
|
Сообщений: 28501
|
|
|
|
Рейтинг: 9796
|
|
Re: головоломка про последовательности
[re: AvovA]
18.01.2010 00:55
|
|
|
А подряд это по окончанию одного другое или со смещением на один символ.
В смысле в 0001 00 два раза подряд или нет?
|
How much wood would woodchuck chuck, if a woodchuck could chuck wood |
|
|
AvovA
|
|
cool russian dude
|
|
|
|
|
|
|
Рег.: 06.11.2002
|
|
Сообщений: 2425
|
|
Из: Toronto, Canada
|
|
Рейтинг: 447
|
|
|
Quote:
В смысле в 0001 00 два раза подряд или нет?
Нет. Совсем подряд, "словослово".
|
пишите письма |
|
|
FrauSoboleva
|
|
Don't Quixote
|
|
|
|
|
|
|
Рег.: 20.11.2004
|
|
Сообщений: 28501
|
|
|
|
Рейтинг: 9796
|
|
Re: головоломка про последовательности
[re: AvovA]
18.01.2010 01:37
|
|
|
Ну я переборчик нашел, не знаю, особо ли красивый.
Отойдем от начала слова символов на 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
Выходит, что двухсимвольных блоков тоже нет.
Значит все трехсимвольные и подряд одинаковые они идти не могут.
Очевиден повтор
|
How much wood would woodchuck chuck, if a woodchuck could chuck wood |
|
|
AvovA
|
|
cool russian dude
|
|
|
|
|
|
|
Рег.: 06.11.2002
|
|
Сообщений: 2425
|
|
Из: Toronto, Canada
|
|
Рейтинг: 447
|
|
|
Да, важно заметить, что "101" и "010" не могут встречаться (в глубине), так перебор упрощается сильно.
Тогда нули и единицы идут только блоками 00, 000, 11, 111.
Quote:
Значит 01
0111001110
Уже повтор, 01110 - 01110 
Cпасибо, думаю, что легче решения уже нет.
|
пишите письма |
|
Список
Плоский
Дерево
