Разделы 
Дополнительно
Задача по математике - 3639
2019-06-13 
Дана конечная последовательность нулей и единиц, обладающая двумя свойствами:
а) если в некотором произвольном месте последовательности выделить 5 цифр подряд и в любом другом месте тоже выделить 5 цифр подряд, то эти пятерки будут различны (эти пятерки могут перекрываться, например $\underbrace {\underbrace {01101}01}$);
б) если к последовательности добавить справа любую цифру 0 или 1, то свойство а) перестает выполняться.
Докажите, что первая четверка цифр нашей последовательности совпадает с последней четверкой.
Решение:
Пусть $abcd$ - четверка последних цифр. В последовательности обязательно встретятся пятерка $abcd0$ (иначе можно было бы добавить 0 с сохранением свойства а), что противоречит б) и $abcd1$. Следовательно, четверка $abcd$ встретится в последовательности трижды, а так как ни 0, ни 1 не могут стоять перед $abcd$ более одного раза, то перед одной из этих четверок не стоит никакой цифры.
Для любого $n$ (в частности, и для $n = 5$) можно расположить $2^n$ цифр 0 и 1 по кругу так, что любое «слово» длины $n$ из 0 и 1 будет встречаться (при обходе против часовой стрелки) ровно один раз. Аналогичный факт верен и в алфавите из любого количества $k \geq 2$ букв (тогда слов длины $n$ будет $k^n$).
Дана конечная последовательность нулей и единиц, обладающая двумя свойствами:
а) если в некотором произвольном месте последовательности выделить 5 цифр подряд и в любом другом месте тоже выделить 5 цифр подряд, то эти пятерки будут различны (эти пятерки могут перекрываться, например $\underbrace {\underbrace {01101}01}$);
б) если к последовательности добавить справа любую цифру 0 или 1, то свойство а) перестает выполняться.
Докажите, что первая четверка цифр нашей последовательности совпадает с последней четверкой.
Решение:
Пусть $abcd$ - четверка последних цифр. В последовательности обязательно встретятся пятерка $abcd0$ (иначе можно было бы добавить 0 с сохранением свойства а), что противоречит б) и $abcd1$. Следовательно, четверка $abcd$ встретится в последовательности трижды, а так как ни 0, ни 1 не могут стоять перед $abcd$ более одного раза, то перед одной из этих четверок не стоит никакой цифры.
Для любого $n$ (в частности, и для $n = 5$) можно расположить $2^n$ цифр 0 и 1 по кругу так, что любое «слово» длины $n$ из 0 и 1 будет встречаться (при обходе против часовой стрелки) ровно один раз. Аналогичный факт верен и в алфавите из любого количества $k \geq 2$ букв (тогда слов длины $n$ будет $k^n$).
