Шахматный жираф

[Ktina]

Шахматная фигура "жираф" -- это конь $1\times 4$, то есть за один ход он перемещается либо на 4 клетки по горизонтали и одну по вертикали, либо на одну по горизонтали и 4 по вертикали.

При каком наименьшем натуральном $n$ жираф может совершить полный обход доски $n\times n$?

[TOTAL]

Ktina в сообщении #627193 писал(а):

При каком наименьшем натуральном $n$ жираф может совершить полный обход доски $n\times n$?

При таком же, при каком сможет слон.

[Ktina]

TOTAL в сообщении #627198 писал(а):

Ktina в сообщении #627193 писал(а):

При каком наименьшем натуральном $n$ жираф может совершить полный обход доски $n\times n$?

При таком же, при каком сможет слон.

Если не секрет, почему?

У слона, вроде, 10 на 10?

[TOTAL]

Ktina в сообщении #627200 писал(а):

Если не секрет, почему?

По ошибке. Я подумал, что у конёвой буквы Г длинная ножка равна 4 клеткам, поэтому конь, как и слон, ходит по клеткам одного цвета.

[Ktina]

Я тоже бред написала про слона

Но слон же может все клетки своего цвета обойти.

Э, нет. Тоже не может.

[Psw]

Ktina в сообщении #627203 писал(а):

Но слон же может все клетки своего цвета обойти.

Э, нет. Тоже не может.

Это почему?
2Х2 свои клетки...

А если, допустим, на диагонали а3-b2-c1 считаем разными рёбрами а3-b2, а3-c1 и b2-c1, то и на любой?

[Ktina]

Psw в сообщении #627232 писал(а):

Ktina в сообщении #627203 писал(а):

Но слон же может все клетки своего цвета обойти.

Э, нет. Тоже не может.

Это почему?
2Х2 свои клетки...

А если, допустим, на диагонали а3-b2-c1 считаем разными рёбрами а3-b2, а3-c1 и b2-c1, то и на любой?

Я про слона на доске 8 на 8 говорила. По-моему, не может.
А с жирафом там ещё интереснее.

-- 05.10.2012, 15:13 --

Тут спрашивают:

Товарищ из лички писал(а):

А тогда сформулируйте, что понимать под "полным обходом"? Надо все клетки посетить ровно по разу или не обязательно по разу, т.е. не менее одного раза?

Отвечаю:
Под полным обходом имеется в виду начать с некоторой клетки, побывать на каждой из остальных клеток ровно по одному разу и вернуться в исходную клетку. Кажется, это называется "гамильтонов цикл"?

[_Ivana]

Ktina в сообщении #627237 писал(а):

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

TOTAL прав, жираф - одноцветная фигура. Если он стоит на белом поле, то он никогда не попадет на черное. Поэтому можно говорить о трех вариантах формулировки задачи:
1) все клетки - решения нет
2) все клетки одного цвета, допустимо в любую клетку заходить неограниченное количество раз
3) все клетки одного цвета, допустимо в любую клетку заходить только один раз

[chessar]

Пока могу предложить следующий результат. Достаточно очевидно, что необходимыми условиями существования Гамильтонова пути $(a,b)$-коня на шахматной доске размером $m\times n$ (где $a<b$, $m\leqslant n$; $a,b,m,n\in\mathbb{N}$) являются условия:
\begin{gather} m\geqslant a+b\\ n\geqslant 2b\\ \text{суммa\;}a+b\text{\;нечётная} \end{gather}
Теперь про $(1,4)$-коня (жирафа) и вообще про $(1,k)$-коня (где $k$ - чётное), которого будем назвать $k$-жирафом ($2$-жираф - это обычный конь получается, а $4$-жираф - обычный жираф). Минимальной доской (в плане размеров $m\times n$, $m\leqslant n$), допускающей Гамильтонов путь $k$-жирафа является доска $(k+1)\times 2k$. Принцип построения одного из таких путей представлен на примерах коня и жирафа:


Для квадратной $4k\times 4k$ доски можно построить путь (пока не привожу). Поэтому для поставленной в теме задачи есть у меня только следующие оценки: $8\leqslant n_{\min{}}\leqslant16$.

Хотя нет, спрашивается ведь про цикл.

_Ivana в сообщении #627431 писал(а):

TOTAL прав, жираф - одноцветная фигура. Если он стоит на белом поле, то он никогда не попадет на черное. Поэтому можно говорить о трех вариантах формулировки задачи:
1) все клетки - решения нет
2) все клетки одного цвета, допустимо в любую клетку заходить неограниченное количество раз
3) все клетки одного цвета, допустимо в любую клетку заходить только один раз

_Ivana, Вы не правы. Под $(1,4)$-конём (жирафом) понимается фигура которая делает 1 ход в одном направлении и 4 хода в перпендикулярном (или наоборот, сначала 4 хода, а потом 1). В итоге получается такая фигура:
\begin{tabular}{|c|c} \hline &\multicolumn{1}{c|}{}\\ \hline & \\ \cline{1-1} & \\ \cline{1-1} &\\ \cline{1-1} &\\ \cline{1-1} \end{tabular}

[_Ivana]

chessar понятно. Я спутал с 3-жирафом, невнимательно прочитал условие.

[chessar]

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

Пусть $G=G(V,E)$ связный граф, степень каждой вершины которого $d(v)\geqslant2$ (это необходимое условие). $|V|=n\geqslant3$.

Обозначим через $J_{k,N\times N}=J_{k,N\times N}(V,E)$ граф, вершинами которого $V$ являются клетки шахматной доски $N\times N$ ($|V|=n=N^2$; далее считаем, что $N\geqslant8$), а его рёбрами $E$ являются неупорядоченные пары клеток, "соединённых" ходом $(1,k)$-коня (или $k$-жирафа, $k$ - чётное), т.е. можно сделать один ход $k$-жирафа из одной клетки пары в другую. Можно заметить, что $\forall v\in V\colon 2\leqslant d(v)\leqslant 8$ для любого $N\geqslant 9$ (при этом существуют вершины всех степеней в этом диапазоне). А вот для $N=8$: $2\leqslant d(v)\leqslant 4$. При этом для любого $N$ ровно 4 вершины имеют степень 2.

Собственно известные критерии для гамильтоновости графа (удовлетворяющего необходимым условиям) используют условия наличия достаточно больших степеней у всех вершин.

1) Условие Дирака. $\left(\forall v\in V: d(v)\geqslant\dfrac{n}{2}\right)\Rightarrow G$\;---\; гамильтонов.
Для нашего $J_{k,N\times N}$ графа, очевидно не применимо.

2) Условие Оре. $\left(\underset{(u,v)\not\in E}{\forall u,v\in V}\colon d(u)+d(v)\geqslant n\right)\Rightarrow G$\;---\; гамильтонов.
Для $J_{k,N\times N}$, очевидно, тоже не применимо, ибо для любых вершин (а не только несмежных) $d(u)+d(v)\leqslant 16$, а у нас $n=N^2\geqslant 64$.

3) Условие Поша. Вводится так называемая функция Поша целого неотрицательного аргумента $x$:

\[ f(x)=\left|\left\{v\in V\mid d(v)\leqslant x\right\}\right| \]

Так вот, если $\underset{1\leqslant x<\frac{n-1}{2}}{\forall x\in\mathbb{Z}}\colon f(x)<x$ и в случае целого $\frac{n-1}{2}\colon f\left(\frac{n-1}{2}\right)\leqslant\frac{n-1}{2}$, то $G$\;---\; гамильтонов.
Для $J_{k,N\times N}\colon f(2)=4>2$ - т.е. тоже не применимо.

4) Теорема Бонди-Хватала тоже не помогает. Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. А замыкание графа определяется добавлением ребра $(u,v)$ для каждой пары несмежных вершин $u$ и $v$, сумма степеней которых не меньше $n$.
Очевидно, что для $J_{k,N\times N}$ замыкание совпадает с самим графом.

Очевидно, что граф $J_{4,9\times9}$ не гамильтонов. Это проясняется следующей картинкой:


Значит имеем следующий промежуточный результат: либо $N_{\min}=8$, либо $N_{\min}\geqslant10$. Есть также гипотеза, что $N_{\min}=10$. Для её подтверждения необходимо доказать, что не существует полного обхода жирафом доски $8\times8$ и представить (или доказать существование) полный обход доски $10\times10$.

[chessar]

chessar в сообщении #627783 писал(а):

Очевидно, что граф $J_{4,9\times9}$ не гамильтонов.

Написал я не точно. Гамильтонов граф ведь по определению тот, который содержит гамильтонову цепь (путь) или гамильтонов цикл. А в этом утверждении понимается именно про гамильтнонов цикл, т.е. $J_{4,9\times9}$ не содержит гамильтонов цикл, т.е. на доске $9\times9$ нет полного обхода жирафом. А вот насчёт гамильтонова пути ничего сказать не могу, возможно он и есть.

[chessar]

Чисто случайно наткнулся на ресурс mayhematics.com, в котором приведено решения для Вашей задачи (и не только). Как я и предполагал, наименьший размер квадратной доски, на которой существует полный обход жирафом - это $10\times10$:

На доске $8\times8$ не только замкнутого маршрута нет, но и не замкнутого тоже, доказательство этого воистину элементарное (см. ссылку). Там же приводится и полный обход для доски $9\times10$ и не замкнутый для $9\times9$.