Псевдо-шахматы на поверхностях

Назовём псевдо-шахматной доской ****на поверхности вложенный в него граф с двумя условиями: валентность каждой вершины этого графа равна $4$, а каждая грань ограничена ровно четырьмя ребрами.

Псевдо-шахматная доска по умолчанию не предполагает раскраски своих клеток в черный и белый цвета, — это только сетка из клеток. Если клетки можно правильно раскрасить в черный и белый цвета как на настоящей шахматной доске, то такая псевдо-шахматная доска называется шахматной доской.

Зафиксируем некоторую развёртку тора, то есть некоторый прямоугольник с отождествленными сторонами, и выделим специальный подкласс псевдо-шахматных досок на торе: (стандартная) псевдо-шахматная доска $n\times m$ — такой граф, который получается из вертикально-горизонтальной сетки $n\times m$ в прямоугольнике после склеивания этого прямоугольника в тор.

Псевдо-шахматная доска $5\times 7$ на развёртке тора.

Стандартное вложение тора в пространство

1. Является ли стандартная псевдо-шахматная доска $5\times 7$ на торе шахматной доской?
2. Опишите все такие пары $(n,m)\in\mathbb{N}\times\mathbb{N}$, для которых стандартная псевдо-шахматная доска $n\times m$ на торе является шахматной доской.
3. Покажите, что слон, стоящий на произвольной клетке стандартной псевдо-шахматной доски $5\times 7$ на торе, бьет любую другую клетку этой псевдо-шахматной доски, а ладья не обладает таким свойством. (Фигуры на псевдо-шахматной доске бьют клетки аналогичным классическому случаю образом — слон бьет по “диагоналям”, а ладья — по “вертикалям” и “горизонталям”.)
4. Как модифицировать стандартную псевдо-шахматную доску $5\times 7$ на торе таким образом, чтобы получилась (не обязательно стандартная) псевдо-шахматная доска с $35$ клетками, на которой ладья смогла бы бить любую клетку из произвольной? (И как при этом изменятся возможности слона?)
5. Могут ли на стандартной псевдо-шахматной доске $8\times 8$ на торе слон и конь одновременно находиться под боем друг друга?
6. Можно ли задать псевдо-шахматную доску на сфере?

Крестики-нолики на поверхностях

На стандартной псевдо-шахматной доске $n\times m$ на торе можно поиграть в крестики-нолики. Правила точно такие же как и в обычных крестиках-ноликах за исключением того, что поле оказывается склеено по краям. Попробуйте поиграть в торические крестики нолики с друзьями!

Победа в торических крестиках-ноликах на доске $3\times 3$

Какой лучший ход для $\textrm{X}$? Какой лучший ход для $\textrm{O}$?

Графы на поверхностях

1. Докажите, что любой конечный граф можно нарисовать ломанными без самопересечений в пространстве.

Граф на $n$ вершинах называется полным, если между любыми двумя его вершинами проведено ребро. Такой граф обозначается через $K_n$.

Граф на $n+m$ вершинах, множество вершин которого разбито на две части, называемые долями, в одной из которых содержится $n$ вершин, а в другой — $m$ вершин, и при этом такой, что имеются все ребра между вершинами из разных долей, и никаких больше, называется полным двудольным и обозначается через $K_{n,m}$.

Развёртка ленты Мёбиуса

Стандартное вложение ленты Мёбиуса в пространство