Преобразования конечных двоичных последовательностей - Шулеры, или Математическое исследование одной карточной игры

Пусть по окружности в некотором порядке расположены N единиц и нулей (исходное состояние S0). Некоторые нули разрешается заменять на единицы в соответствии с правилами игры (N, k) (пп. 1.1-1.2.).

    1) При каких условиях из произвольной последовательности S0 Можно получить последовательность, состоящую из одного нуля и N-1 единицы? 2) При каких условиях мы можем получить последовательность, состоящую из T = D(N, k) единиц?

Две конечные последовательности эквивалентны, если обе при правильной игре типа А или В приводятся к одной и той же конечной последовательности нулей и единиц.

Теорема 5. Если при перестановке типа PK из последовательности S0 получится двоичное число (2P-1)2Q, где 0 ? P+Q ? N, то последовательность S0 эквивалентна последовательности (1,1,...,1,0)

Теорема 6. Если при перестановке типа PK из последовательности S0 получится двоичное число вида ((2PJ-1)2QJ)2KJ, где 0 ? P+Q ? n/D, то последовательность S0 эквивалентна последовательности (111...110111...1110). (d отрезков последовательности, каждый из которых состоит из -1 единиц и одного нуля)

Теорема 7. Последовательность S0 мы можем получить из нулевой последовательности тогда и только тогда, когда ни одна компонента последовательности S0 не состоит из одних единиц.

Доказательство теоремы 5. Если перестановка PK имеет вид 00...00111...111000, то метод, по которому все остальные нули, кроме одного, превращаются в единицы, описан в п. 2.1. Из того же пункта можно видеть, что перестановки типа PK другого вида к искомой последовательности не приводится.

Теорема 6 доказывается аналогично.

7. Докажем сначала для k=1.

Пронумеруем числа (как на исходном кругу, так и на нулевом кругу) числами от 1 до N по часовой стрелке. Пусть K-ое число на исходном кругу - нуль. Тогда будем двигаться по нулевому кругу, взяв за начало движения K-ый нуль и двигаясь против часовой стрелки, и будем рассматривать каждый встречающийся нам нуль. Пусть сейчас мы рассматриваем M-тый нуль. Тогда, если m-тое число на исходном кругу - единица, заменим на нулевом кругу M_Тый нуль единицей (мы можем это сделать, т. к. M-1-ое число на нулевом кругу на данной стадии нуль). Таким образом, обойдя нулевой круг, мы превратим его в исходный.

Исключение составляет случай, когда исходный круг состоит из одних единиц (то, что мы не можем получить такой круг, мы уже доказали - аналогичное утверждение доказывалось нами при рассмотрении карточной задачи).

При K > 1 утверждение доказывается аналогично.

Похожие статьи




Преобразования конечных двоичных последовательностей - Шулеры, или Математическое исследование одной карточной игры

Предыдущая | Следующая