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
|
Сообщений: 28497
|
|
Рейтинг: 9788
|
|
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
|
Сообщений: 28497
|
|
Рейтинг: 9788
|
|
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пасибо, думаю, что легче решения уже нет.
|
пишите письма |
|