2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Открытые туры предвзятой ладьи (проверка доказательств)
Сообщение23.11.2021, 19:27 
Аватара пользователя


22/11/13
02/04/25
549
У нас есть простая структура - предвзятая ладья двух типов. Здесь и далее открытый тур тождественен Гамильтонову пути.

Предвзятая ладья первого рода совершает открытые туры на специфической доске $f(n)\times 1$ , где $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$, а ячейки окрашены в белый или черный цвет в соответствии с двоичным представлением $2n$. Ячейка окрашивается в белый цвет, если двоичная цифра равна $0$, и ячейка окрашивается в черный цвет, если двоичная цифра равна $1$. Предвзятая ладья на белой клетке движется только влево и в противном случае движется в любом направлении.

Предвзятая ладья второго рода совершает открытые туры на специфической доске $f(n)\times 1$ , где $f(n) = \left\lfloor\log_2{2n}\right\rfloor + 1$, а ячейки окрашены в белый или черный цвет в соответствии с двоичным представлением $2n$. Ячейка окрашивается в белый цвет, если двоичная цифра равна $0$, и ячейка окрашивается в черный цвет, если двоичная цифра равна $1$. Предвзятая ладья на белой клетке движется только влево и в противном случае движется только вправо.

Пусть $a_1(n)$ (A284005) - число открытых туров предвзятой ладьей первого рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на любой клетке. Тогда имеет место быть рекурсия
$$a_1(n)=(1+\operatorname{wt}(n))a_1(\left\lfloor\frac{n}{2}\right\rfloor), a_1(0)=1$$
где $\operatorname{wt}(n)$ (A000120) - число единиц в двоичной записи $n$.

Как это можно доказать? Начнем с доски, заполненной лишь черными клетками, коих у нас будет $k$ штук.
$$\underbrace{1\cdots1}_{k}$$
Исходную клетку мы выбираем $k$ способами. По условию предвзятая ладья на черной клетке движется в любом направлении, соответственно следующую мы выбираем $k-1$, третью - $k-2$ способами и т.д. По итогам имеем $k!$ открытых туров.

Добавим белую клетку где-нибудь посредине между черными:
$$\underbrace{1\cdots1}_{k_2}0\underbrace{1\cdots1}_{k_1}$$
Представим, что ее как и ранее нет, тогда мы вновь начинаем с $k!$ открытых туров. Теперь зададимся вопросом: сколькими способами мы можем вставить белую клетку в последовательность посещения черных? Пусть $1_1$ это черные клетки справа от белой, а $1_2$ - черные клетки слева. Разберем на примере:
$$1_11_21_21_11_11_2$$
Очевидно, что перед $1_1$ белая клетка стоять не может, поскольку предвзятая ладья на белой клетке движется только влево. Отметим возможные и невозможные положения через $+$ и $-$:
$$-1_1+1_2+1_2-1_1-1_1+1_2+$$
Как мы видим на примере, белая клетка может стоять перед любой из $1_2$ плюс в конце. Домножая на $k!$ имеем $k!(k_2+1)$ открытых туров.

Добавим еще одну белую клетку справа от предыдущей и аналогично разберем на примере:

$$-1_1+1_2+0-1_2-1_1-1_1+1_2+$$

Ввиду того, что клетка расположена справа, перейти на нее с предыдущей белой мы не можем, что и отражено $-$ после $0$. Зная, что исходная белая клетка может стоять лишь перед $1_2$, мы все также имеем $k_2+1$ способов. Домножая, имеем $k!(k_2+1)^2$ открытых туров. Аналогично для
$$\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j}\underbrace{1\cdots1}_{k_1}$$
имеем $k!(k_2+1)^j$ открытых туров. Далее добавляем белые клетки справа:
$$\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$
Разберем на примере:
$$+1_1+0_2-1_2+0_2-1_2+1_1+1_1+1_2+$$
Здесь мы уже можем перемещаться как на $1_2$, так и на $1_1$. После $0_2$ белая клетка $0_1$ стоять не может, итого имеем $(k_1+k_2+1)$ способов. По аналогии в итоге будем иметь $k!(k_2+1)^{j_2}(k_1+k_2+1)^{j_1}$.

Разбирая аналогичные примеры для
$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1}$$
имеем
$$k!(k_m+1)^{j_m}(k_{m-1}+k_m+1)^{j_{m-1}}\cdots(k_2+\cdots+k_m+1)^{j_2}(k_1+k_2+\cdots+k_m+1)^{j_1}$$
где $k=k_1+k_2+\cdots+k_m$. Компактно выражение выше можно записать через
$$a_1(n)=\left(\sum\limits_{i=1}^{m}k_i\right)!\prod\limits_{p=1}^{m}\left(1+\sum\limits_{q=p}^{m}k_q\right)^{j_p}$$
Вот код на pari для проверки:
Код:
default(parisizemax,10^9)
n=5
T(n,k)=if(n>0,if(k==0,valuation(n,2)+1,T(n\2,k-n%2)),0)
A003188(n)=bitxor(n, n>>1)
R(n,k)=T(A003188(n),k)
v=vector(2^n-1,i,vector(hammingweight(A003188(i)),j,R(i,j-1)))
for(i=1,2^n-1,print(v[i])) \\ просмотр массива ранов нулей и единиц в n
A069010(n)=(1 + (hammingweight(bitxor(n, n>>1)))) >> 1
a(n)=if(n==0,1,(sum(i=1,A069010(n),v[2*n][2*i]))!*prod(p=1,A069010(n),(1+sum(q=p,A069010(n),v[2*n][2*q]))^v[2*n][2*p-1]))
for(i=0,2^(n-1)-1,print(a(i)))

Имея теперь выражение для $a_1(n)$, докажем рекурсию. Здесь надо вернуться к началу и еще раз подчеркнуть, что
Цитата:
Пусть $a_1(n)$ (A284005) - число открытых туров предвзятой ладьей первого рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на любой клетке.

Т.е. в конце у нас всегда будет как минимум один $0$.

Начнем с $a(2n)$. Добавляя $0$ к последовательности нулей длиной $j_1$ имеем
$$a_1(2n)=\left(\sum\limits_{i=1}^{m}k_i\right)!\prod\limits_{p=1}^{m}\left(1+\sum\limits_{q=p}^{m}k_q\right)^{j_p+[p=1]}=\left(1+\sum\limits_{q=1}^{m}k_q\right)a_1(n)=(1+\operatorname{wt}(n))a_1(n)$$
Теперь разберем $a_1(2n+1)$. Возможны два случая:
$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}1\underbrace{0}_{j_1}$$
и
$$\underbrace{1\cdots1}_{k_m}\underbrace{0\cdots0}_{j_m}\cdots\underbrace{1\cdots1}_{k_2}\underbrace{0\cdots0}_{j_2}\underbrace{1\cdots1}_{k_1}\underbrace{0\cdots0}_{j_1-1}\underbrace{1}_{k_0}\underbrace{0}_{j_0}$$
В первом у нас
$$a_1(2n+1)=(\sum\limits_{i=1}^{m}k_i+[i=1])!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q+[q=1])^{j_{p}}=(2+\sum\limits_{q=1}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=2}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}$$$$a_1(2n+1)=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a_1(n)$$
А во втором
$$a_1(2n+1)=(1+\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=0}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_{p}-[p=1]}=(1+\sum\limits_{q=0}^{m}k_q)(1+\sum\limits_{i=1}^{m}k_i)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p-[p=1]}$$$$a_1(2n+1)=(2+\sum\limits_{q=1}^{m}k_q)(\sum\limits_{i=1}^{m}k_i)!\prod\limits_{p=1}^{m}(1+\sum\limits_{q=p}^{m}k_q)^{j_p}=(2+\operatorname{wt}(n))a_1(n)$$
По совокупным итогам имеем
$$a_1(2n)=(1+\operatorname{wt}(n))a_1(n)=(1+\operatorname{wt}(2n))a_1(n)$$$$a_1(2n+1)=(2+\operatorname{wt}(n))a_1(n)=(1+\operatorname{wt}(2n+1))a_1(n)$$
Что и требовалось доказать.

И еще одна маленькая деталь.

Пусть $a_2(n)$ (A329369) - число открытых туров предвзятой ладьей второго рода на соответствующей доске (двоичное представление $2n$), оканчивающихся на белой клетке. Тогда имеет место быть трансформация
$$a_1(n) = \sum\limits_{k=0}^{n}(\binom{n}{k}\bmod 2)a_2(k)$$
Как это можно доказать? Рассмотрим на примере небольшой доски, скажем $1100$. Заменим последовательно $k$ единиц $k$ нулями:

  • $1100$ - без изменений ($0$ единиц заменено $0$ нулями)
  • $0100$ - $1$ единица заменена $1$ нулем
  • $1000$ - другой вариант предыдущего
  • $0000$ - $2$ единицы заменено $2$ нулями

Результирующие значения $0,2,4,6$ (ввиду того, что, опять-таки, мы работаем с двоичным представлением $2n$) это и есть суммируемые $a_2(k)$, такие, что $\binom{n}{k}\bmod 2=1$. В каждом из случаев мы суммировали пути, оканчивающиеся лишь на белых клетках, но т.к. черные были заменены на белые, мы по итогам имеем все возможные пути, оканчивающиеся на всех клетках.

Что и требовалось доказать.

Насколько строгими можно назвать доказательства? Требуют ли они уточнений? Могут ли они быть улучшены (например каким-нибудь образом упрощены)?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: confabulez


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group