2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Король на шахматной доске
Сообщение16.07.2009, 13:08 
Заморожен
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 15:04 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Профессор Снэйп в сообщении #229386 писал(а):
Всегда ли шахматный король может перейти с одного из краёв этой доски на противоположный край, шагая только по клеткам одного цвета?
Сначала заставим снизу вверх по белым клеткам исходить все, что только можно, ладью. Если ладья не смогла добраться до верха и со злости уничтожила все клетки на которых смогла побывать, то по краю обрыва по черным клеткам, стартуя с самой нижней, слева направо пересечет доску король.

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 16:33 
Заморожен
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 19:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 23:08 


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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 23:17 
Заслуженный участник


04/05/09
4582
Vanuan в сообщении #229549 писал(а):
Во-первых, король движется в любом направлении, а не только по клеткам одного цвета. Ну что ж, допустим, нет требуемой фигуры.
Во-вторых, не указано, есть ли другие фигуры на доске.
В-третьих, доска не шахматная, она прямоугольная, размером mxn. Кроме того, добавлен элемент случайности - "клетки раскрашены произвольным образом"
В-четвёртых, не указано, в каком диапазоне находятся m и n.

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

Vanuan в сообщении #229549 писал(а):
Или нужно доказательство? Не понимаю, где подвох?
К ответу "не всегда" неплохо бы приложить пример.

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение16.07.2009, 23:38 


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

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

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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 07:09 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Vanuan в сообщении #229556 писал(а):
Следовательно король всегда сможет перейти от любой стороны к противоположной.
На черной доске от верха до низа идет белая полоса. Чтобы добраться с левой границы до правой (по черным клеткам, других на этих границах нет), корольку придется пересесть на конька (иначе не преодолеет белую полосу). Так что не всегда он сможет перейти от любой стороны к противоположной.

Профессор Снэйп в сообщении #229456 писал(а):
Да, но там же этот "обрыв" может оказаться очень неровным. Например, на одной вертикали могут присутствовать несколько чёрных клеток, перемежаемых клетками обрыва.

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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 09:08 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Пусть $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$?

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 11:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 12:22 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
TOTAL в сообщении #229633 писал(а):
Если полетят искры, то можно по меди добраться с низа до верха (ведь ток добрался!). Если искр не будет, то по фарфору доползем с левой границы до правой.


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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 12:41 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 12:43 
Заморожен
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 12:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Король на шахматной доске
Сообщение17.07.2009, 13:00 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Профессор Снэйп в сообщении #229657 писал(а):
Контрпример к утверждению

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу 1, 2, 3  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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