Справедливо ли, что в двоичной бесконечной
непериодической последовательности
встречаются любые подпоследовательности
длиной m для произвольного m?

Да.

В случае, если в последовательности бесконечное число нулей и единиц, мы можем найти первый член
нашей будущей подпоследовательности, после него также будет бесконечное число нулей и единиц,
значит найдём и второй член, и т.д. Процесс конечен и выполним.

На, а случая, когда нулей или единиц конечное число не бывает: иначе после последней "конечной"
цифры все члены будут одинаковы — последовательность переодична.

Здравствуйте, mrhru, Вы писали:

M>Справедливо ли, что в двоичной бесконечной
M>непериодической последовательности
M>встречаются любые подпоследовательности
M>длиной m для произвольного m?

Да. Пусть w — любая бесконечная непериодическая последовательность, x — искомая подпоследовательность, |x|=m.

Если x_1==0, то находим первый нуль в w (нуль существует, поскольку w не может состоять из одних единиц, поскольку w — непериодическая). Пусть i_1 = индексу этого нуля в w.
Если x_1==1, то находим первую единицу в w (единица существует, поскольку w не может состоять из одних нулей, поскольку w — непериодическая). Пусть i_1 = индексу этой единицы в w.

Рассуждения повторяем для w'=<оставшийся хвост от w> и x'=<биты со 2-го по m-й>. Получим w'' и x''. И так далее.

В результате полученный набор индексов и есть искомая подпоследовательность.

Здравствуйте, Александр Сомов, Вы писали:

АС>Да.

АС>В случае, если в последовательности бесконечное число нулей и единиц, мы можем найти первый член
АС>нашей будущей подпоследовательности, после него также будет бесконечное число нулей и единиц,
АС>значит найдём и второй член, и т.д. Процесс конечен и выполним.

Извиняюсь, имелось ввиду: "встречаются любые подпоследовательности длиной m"
— m рядом расположенных символов.

АС>На, а случая, когда нулей или единиц конечное число не бывает: иначе после последней "конечной"
АС>цифры все члены будут одинаковы — последовательность переодична.

Согласен.

(Собственно, с моей стороны это не задача, это вопрос)

По-видимому, надо как-то уточнить термин "периодическая последовательность".

Например, последовательность 100000000... будем считать периодической.

Т.е. периодическая последовательность — это последовельность, которая начиная с некоторой позиции, начинает повторятся. (тавтология, но надеюсь смысл понятен). Так?

Кстати, нашёл пример непериодической последовательности, которая не удовлетворяет
условию задачи:
10110111011110111110111110111...
т.е. за n единицами следует 0, затем n+1 единица с нулём и т.д.

Очевидно, что эта последовательность непериодическая и в ней нет подпоследовательности включающей подряд два нуля.

Поэтому, вопрос ставим по другому:

Справедливо ли, что в двоичной бесконечной непериодической
последовательности встречаются m подряд следующих символов
0 или 1 для произвольного m?

M>Поэтому, вопрос ставим по другому:
M>

M>Справедливо ли, что в двоичной бесконечной непериодической
M>последовательности встречаются m подряд следующих символов
M>0 или 1 для произвольного m?

А вот это уже неверно:

Рассмотрим последовательность a_i : 1,2,1,2,2,1,2,2,2,1,2,2,2,2 ... 1, n двоек, 1, (n+1) двоек ...
А теперь будем строить следующую последовательность:

a_1 единиц, 0, a_2 единиц, 0, a_3 единиц, 0 ...

Она непериодическая, и в ней нет 3-х подряд идущих 0, либо 3-х подряд идущих 1.

Здравствуйте, Александр Сомов, Вы писали:

M>>Поэтому, вопрос ставим по другому:
M>>

M>>Справедливо ли, что в двоичной бесконечной непериодической
M>>последовательности встречаются m подряд следующих символов
M>>0 или 1 для произвольного m?

АС>
АС>А вот это уже неверно:

АС>Рассмотрим последовательность a_i : 1,2,1,2,2,1,2,2,2,1,2,2,2,2 ... 1, n двоек, 1, (n+1) двоек ...
АС>А теперь будем строить следующую последовательность:

АС>a_1 единиц, 0, a_2 единиц, 0, a_3 единиц, 0 ...

АС>Она непериодическая, и в ней нет 3-х подряд идущих 0, либо 3-х подряд идущих 1.

Хорошее опровержение!!!

Здравствуйте, Александр Сомов, Вы писали:

АС>А вот это уже неверно:

АС>Рассмотрим последовательность a_i : 1,2,1,2,2,1,2,2,2,1,2,2,2,2 ... 1, n двоек, 1, (n+1) двоек ...
АС>А теперь будем строить следующую последовательность:

АС>a_1 единиц, 0, a_2 единиц, 0, a_3 единиц, 0 ...

АС>Она непериодическая, и в ней нет 3-х подряд идущих 0, либо 3-х подряд идущих 1.

ИЗВИНИТЕ, НО ОТКУДА У ВАС В ДВОИЧНОЙ ПОДПОСЛЕДОВАТЕЛНОСТИ ДВОЙКИ ВЗЯЛИСЬ??? Это уже троичная подпоследовательноять!!!

Читайте внимательно.

Здравствуйте, adontz, Вы писали:

АС>Рассмотрим последовательность a_i : 1,2,1,2,2,1,2,2,2,1,2,2,2,2 ... 1, n двоек, 1, (n+1) двоек ...
АС>А теперь будем строить следующую последовательность:
АС>a_1 единиц, 0, a_2 единиц, 0, a_3 единиц, 0 ...

Последовательность бинарная, такая:

1 0 11 0               // соответствует 1,2
1 0 11 0 11 0          // соответствует 1,2,2
1 0 11 0 11 0 11 0 ... // соответствует 1,2,2,2

Подобные последовательности называются бескубными, и их вообще море.

Здравствуйте, LCR, Вы писали:

LCR>Последовательность бинарная, такая:
LCR>

LCR>1 0 11 0               // соответствует 1,2
LCR>1 0 11 0 11 0          // соответствует 1,2,2
LCR>1 0 11 0 11 0 11 0 ... // соответствует 1,2,2,2
LCR>

LCR>Подобные последовательности называются бескубными, и их вообще море.

Но это периодическая последовательность
ИМХО утверждение верно

LCR>Последовательность бинарная, такая:
LCR>

LCR>1 0 11 0               // соответствует 1,2
LCR>1 0 11 0 11 0          // соответствует 1,2,2
LCR>1 0 11 0 11 0 11 0 ... // соответствует 1,2,2,2
LCR>

LCR>Подобные последовательности называются бескубными, и их вообще море.

A>Но это периодическая последовательность
A>ИМХО утверждение верно

Последовательность такая:

1 0 11 0 \
1 0 11 0 11 0 \
1 0 11 0 11 0 11 0 \
1 0 11 0 11 0 11 0 11 0 ...

или же (в одной строке) 10110101101101011011011010110110110110 ...

Попробуйте найти у неё конечный период.

Утверждение неверно. Строим последовательность:
0,1,0,0,1,0,0,0,1,0,0,0,0,1 и т.д.
сначала n нулей, затем 1, затем n+1 нулей, затем 1 и т.д.
Она не периодическая (очевидно). Но комбинация 11 в ней не присутствует.
"LCR" <forum@rsdn.ru> wrote in message news:263750@news.rsdn.ru...
From: LCR нет

Здравствуйте, mrhru, Вы писали:

M>Справедливо ли, что в двоичной бесконечной
M>непериодической последовательности
M>встречаются любые подпоследовательности
M>длиной m для произвольного m?

Да. Пусть w — любая бесконечная непериодическая последовательность, x — искомая подпоследовательность, |x|=m.

Если x_1==0, то находим первый нуль в w (нуль существует, поскольку w не может состоять из одних единиц, поскольку w — непериодическая). Пусть i_1 = индексу этого нуля в w.
Если x_1==1, то находим первую единицу в w (единица существует, поскольку w не может состоять из одних нулей, поскольку w — непериодическая). Пусть i_1 = индексу этой единицы в w.

Рассуждения повторяем для w'=<оставшийся хвост от w> и x'=<биты со 2-го по m-й>. Получим w'' и x''. И так далее.

В результате полученный набор индексов и есть искомая подпоследовательность.
Оценить

Здравствуйте, Евгений Коробко, Вы писали:

ЕК>Утверждение неверно. Строим последовательность:
ЕК>0,1,0,0,1,0,0,0,1,0,0,0,0,1 и т.д.
ЕК>сначала n нулей, затем 1, затем n+1 нулей, затем 1 и т.д.
ЕК>Она не периодическая (очевидно). Но комбинация 11 в ней не присутствует.

Ну и, пардон, что здесь нового? Об этом уже десять человек написали!
Изначально задача была сформулирована не точно.
Если считать, что ищется произвольная комбинация идущих подряд символов, то ответ нет. Если произвольная подпоследовательность, то ответ да.

Здравствуйте, Евгений Коробко, Вы писали:

ЕК>Утверждение неверно. Строим последовательность:
ЕК>0,1,0,0,1,0,0,0,1,0,0,0,0,1 и т.д.
ЕК>сначала n нулей, затем 1, затем n+1 нулей, затем 1 и т.д.
ЕК>Она не периодическая (очевидно). Но комбинация 11 в ней не присутствует.

Боюсь, ты неправильно понимаешь термин "подпоследовательность". Подпоследовательность 11 в построенной тобой последовательности присутствует: возьми элемент с индексом 1 и с индексом 4 — вот и всё.