Король на шахматной доске

[Профессор Снэйп]

Пусть есть прямоугольная "шахматная" доска размером $m \times n$. Клетки доски раскрашены произвольным образом в два цвета.

Всегда ли шахматный король может перейти с одного из краёв этой доски на противоположный край, шагая только по клеткам одного цвета?

[TOTAL]

Профессор Снэйп в сообщении #229386 писал(а):

Всегда ли шахматный король может перейти с одного из краёв этой доски на противоположный край, шагая только по клеткам одного цвета?

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

[Профессор Снэйп]

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

Я понимаю, что, скорее всего, какой-то путь именно по краю обрыва будет. Возможно, с возвращениями после захождений в тупики. Но как бы это доказать построже?

[worm2]

Можно изящно сформулировать более сильное утверждение TOTAL так:
Граница "4-связной" области является "8-связной".
Верно также утверждение, что граница "8-связной" области является "4-связной" (надеюсь, понятно, какой смысл я пытаюсь вложить в понятия "4-связность" и "8-связность").
Интуитивно эти утверждения очевидны, но вот как строго доказать их так же непринуждённо...

[Vanuan]

Во-первых, король движется в любом направлении, а не только по клеткам одного цвета. Ну что ж, допустим, нет требуемой фигуры.
Во-вторых, не указано, есть ли другие фигуры на доске.
В-третьих, доска не шахматная, она прямоугольная, размером mxn. Кроме того, добавлен элемент случайности - "клетки раскрашены произвольным образом"
В-четвёртых, не указано, в каком диапазоне находятся m и n.

Вопрос простой. Простой ответ - не всегда. Или нужно доказательство? Не понимаю, где подвох?

[venco]

Vanuan в сообщении #229549 писал(а):

Во-первых, король движется в любом направлении, а не только по клеткам одного цвета. Ну что ж, допустим, нет требуемой фигуры.
Во-вторых, не указано, есть ли другие фигуры на доске.
В-третьих, доска не шахматная, она прямоугольная, размером mxn. Кроме того, добавлен элемент случайности - "клетки раскрашены произвольным образом"
В-четвёртых, не указано, в каком диапазоне находятся m и n.

Вопрос простой. Простой ответ - не всегда.

Ответ неверный.

Vanuan в сообщении #229549 писал(а):

Или нужно доказательство? Не понимаю, где подвох?

К ответу "не всегда" неплохо бы приложить пример.

[Vanuan]

И кстати, что значит "с одного края на противоположный"? То есть король может начать с ЛЮБОЙ клетки ЛЮБОГО края и должен закончить любой клеткой противоположного края? Тогда задача становится более осмысленной.

-- Пт июл 17, 2009 00:20:42 --

Значит, всегда. Задача сводится к раскраске плоского полносвязного графа из четырёх вершин двумя цветами. Это невозможно.
Доказательство:
Пусть A,B,C,D - множества клеток каждой четверти доски.
Для того, чтобы король не мог перейти от одного края к другому, необходимо и достаточно, чтобы А, B, C и D были раскрашены разными цветами. Так как цвета всего два, это невозможно. Следовательно король всегда сможет перейти от любой стороны к противоположной.

Любой полносвязный граф из n вершин для правильной раскраски требует n цветов. В данном случае 4. Задача была бы немного интересней, если бы цветов было 3. В случае 4 цветов ответ - не всегда.

[TOTAL]

Vanuan в сообщении #229556 писал(а):

Следовательно король всегда сможет перейти от любой стороны к противоположной.

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

Профессор Снэйп в сообщении #229456 писал(а):

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

Я понимаю, что, скорее всего, какой-то путь именно по краю обрыва будет. Возможно, с возвращениями после захождений в тупики. Но как бы это доказать построже?

Построже. Ряд клеток ниже доски разрушим. Вдоль каждого звена обрыва нарисуем стрелку (при движении вдоль стрелки обрыв справа). В каждый узел (общая часть четырех соседних клеток) приходит столко же стрелок, сколько выходит из него. Встанем на какую-нибудь из стрелок, что расположены ниже доски. Идем по стрелкам, стирая те, по которым уже прошли. Очевидно, что неизбежно вернемся на место старта, т.е. были и на левом и на правом краях доски.

[Профессор Снэйп]

Пусть $f : [0,1]^2 \to [0,1]$ --- непрерывная функция, $[0,1] = A \cup B$ и $A \cap B = \varnothing$. Всегда ли существует непрерывная функция $g : [0,1] \to [0,1]^2$, такая что

1) $g(0)$ и $g(1)$ лежат на противоположных сторонах квадрата $[0,1]^2$;
2) $f(g([0,1])) \subseteq A$ или $f(g([0,1])) \subseteq B$?

[TOTAL]

Даже непрерывность функции $f$ не нужна, в чем можно убедиться, проделав следующий эксперимент. Все точки квадратной пластины, для которых $f(x,y) \subseteq A$, изготовим из меди, а остальные точки сделаем из фарфора. По всей длине нижней и верхней границы квадратной пластины приложим по контакту и соединим их с соответствующей дыркой розетки. Если полетят искры, то можно по меди добраться с низа до верха (ведь ток добрался!). Если искр не будет, то по фарфору доползем с левой границы до правой.

[Профессор Снэйп]

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

Если полетят искры, то можно по меди добраться с низа до верха (ведь ток добрался!). Если искр не будет, то по фарфору доползем с левой границы до правой.

Почему это так? Мне вот сомнительно. Почему не может быть ситуации, когда и по меди, и по фарфору не доберёмся?

[TOTAL]

Может, даже посильней сформулировать?
Для непрерывной функции $f$ найдется линия уровня, соединяющая две противоположные стороны.
Есть пример, опровергающий это утверждение?

[Профессор Снэйп]

Контрпример к утверждению "если не по меди снизу вверх, то по фарфору слева направо" строится довольно просто. Возьмём график функции

$$ f(x) = \begin{cases} \sin(1/x), &x \neq 0 \\ 0, &x = 0 \end{cases} $$

выложим его медью на фарфоровой плоскости. Потом вырежем квадрат $[-1/2,1/2]^2$ и развернём его на 90 градусов.

[ИСН]

Нет, это как раз фигня: обходится по фарфору снизу вверх.

[TOTAL]

Профессор Снэйп в сообщении #229657 писал(а):

Контрпример к утверждению

Не понимаю этот контрпример. Полно дорог слева направо получается.