Решение задачи 7.
Последовательность строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 0, т.е.
0 -> 01 -> 0110 -> 01101001 ->...
Докажите, что предложенная последовательность удовлетворяет условию задачи.
Если не смогли этого сделать, то вот доказательство:
Будем нумеровать цифры последовательности, начиная с нуля. Итак, a(0)a(1)=01, a(2)a(3)=10=a(1)a(0). Отметим, что последовательность состоит из 'кирпичиков' 01 и 10 (любые a(2k)a(2k+1) есть либо a(0)a(1), либо a(1)a(0)). Любой отрезок четной длины, начинающийся с элемента с четным индексом a(2k) имеет поровну нулей и единиц. Предположим, что в M есть три смежных одинаковых отрезка. Если есть такие отрезки, то есть и отрезки минимальной длины. Можно считать, что сначала идет начальный отрезок P, затем подряд три смежных одинаковых отрезка S1,S2 и S3 минимальной длины, S1=S2=S3= =S:
P S1 S2 S3.
Будем обозначать длину отрезка A через IAI.
Есть 4 возможных варианта:
1) IPI=2k, ISI=2l.
Будем писать 0* вместо 01 и 1* вместо 10. С помощью этих символов последовательность M записывается так же, как и раньше:
M=0*1*1*0*1*0*0* ...
Значит и P, и S можно записать с помощью символов 0* и 1*; начальный отрезок P будет состоять из k знаков 0* и 1*, а S - из l знаков. Уберем звездочки у цифр - последовательность M от этого не изменится. А из P,S1,S2 и S3 мы получим новые отрезки P', S1',S2' и S3' с длинами вдвое меньшими. Отрезки S1',S2' и S3' остаются одинаковыми, а длина каждого из них станет l. Мы получили противоречие с утверждением о минимальности длины S.
2) IPI=2k, ISI=2l+1.
Отрезок S1 начинается элементом с четным индексом. Длина отрезка S1 S2 четная (она равна 4l+2), и в нем одинаковое число нулей и единиц. Длина S1 нечетная, и, без нарушения общности, предположим, что нулей в S1 больше, чем единиц, тогда в S2 единиц будет больше чем нулей?! Противоречие с тем, что S1=S2.
3) IPI=2k+1, ISI=2l+1.
Отрезок S2 S3 имеет четную длину и начинается элементом с четным индексом. Далее рассуждения аналогичны приведенным в пункте 2.
4) IPI=2k+1, ISI=2l.
Последний элемент отрезка P имеет индекс a(2k) (вспомните, что нумерация элементов начинается с нуля). Пара a(2k) a(2k+1) есть либо 01, либо 10, и всегда a(2k)<>a(2k+1). Первые элементы S1,S2 и S3 будут, соответственно, a(2k+1), a(2k+2l+1), a(2k+4l+1). Поэтому из совпадения S1=S2=S3 следует, что
a(2k+1)=a(2k+2l+1)=a(2k+4l+1)<>a(2k)=a(2k+2l)=a(2k+4l)
Следовательно, так как
a(2k)a(2k+1)=a(2k+2l)a(2k+2l+1)=a(2k+4l)a(2k+4l+1),
то мы можем считать, что повторяющиеся отрезки S1 S2 S3 начинаются в позиции a(2k), IPI=2k, ISI=2l, а этот случай уже разобран в пункте 1.
|
