Задача о шахматном коне

[Fedya]

Доброго времени суток, уважаемые форумчане. Помогите решить задачу про шахматного коня!

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

Заранее благодарен!

[Toucan]

Собственные мысли изложите, пожалуйста.

[Fedya]

Пока ничего толкового в голову не пришло. Можно сказать что есть это переход между клеточками одного цвета, то ходов нужно выполнить 2;4 или 6. Если между клеточками разных цветов, то 1;3 или 5

[ИСН]

Что значит "определить расстояние"?

-- Ср, 2012-08-29, 01:20 --

а то я уже два смысла придумал. Один про аксиомы метрики, а другой - - -

[Fedya]

расстояние это наименьшее количество ходов конем, которые нужно сделать, чтобы добраться от одной клеточки до другой

[ИСН]

И что? У Вас вызывает сомнения, что от любой до любой другой клеточки можно добраться?

[Fedya]

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

[Someone]

Fedya в сообщении #612067 писал(а):

Я так понял, что нужно доказать то, что если заданы координаты двух клеточек, то не выполняя построения (не пользуясь доской) возможно сказать сколько минимально нужно выполнить ходов конем чтобы перейти от одно до другой клеточки

То есть, Вы рассчитываете на какую-нибудь более-менее сложную формулу? Боюсь, это будет весьма затруднительно.

Пусть заданы две клеточки на доске. Одну из них пометим числом $0$. Можно ли найти клеточки, которые находятся от неё на расстоянии $1$?

[Fedya]

Вот как раз на формулу я и не рассчитываю, потому как вопрос в задаче стоял бы по другому. Вот сижу сейчас, строю фигуры различные, что-то вроде наклевывается, но пока результата нет(

-- 29.08.2012, 01:58 --

Someone в сообщении #612070 писал(а):

Пусть заданы две клеточки на доске. Одну из них пометим числом $0$. Можно ли найти клеточки, которые находятся от неё на расстоянии $1$?

Можно. Только вот как правильно задать номера клеточкам? Шахматное обозначение наверное не подойдет

[longstreet]

Замкнутая формула приведена здесь: http://apetresc.wordpress.com/2010/10/2 ... ht-metric/

И в Кванте "Метрика коня": http://kvant.mccme.ru/1981/10/metrika_konya.htm (правда, там для близких клеток к начальному расположению коня формула не работает).

Вообще, у коня кривая метрика. Окружности, например, некрасивые...

Fedya в сообщении #612074 писал(а):

Только вот как правильно задать номера клеточкам?

Например, так:

(Оффтоп)

Fedya в сообщении #612005 писал(а):

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

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

[ИСН]

Fedya, ещё раз: что Вы ищете? Если на формулу не рассчитываете (и правильно делаете), то что? Доказательство, что между любыми клеточками существует минимальный путь? А Вы поймёте, что это оно, когда увидите?
Как насчёт такого, например: построим между клеточками любой путь. (Что он вообще есть, показывается отдельно и просто.) Положим, в нём 100 ходов. Теперь рассмотрим все маршруты, начинающиеся с первой клетки и состоящие из 100 ходов. Их будет довольно много, но всё-таки конечное число. Какие-то из них не придут во вторую клетку никогда; эти отбросим. Какие-то придут на 100-м ходу или раньше. Вот из этих выберем тот, который придёт раньше всего.
И пусть кто-нибудь попробует сказать, что это неконструктивно.

[Fedya]

Пусть М - множество клеточек шахматной доски 8х8. Расстояние d(x;y) между двумя клеточками х и у определяется как минимальное количество шагов коня, которые нужно выполнить, чтобы попасть с х в у.
1) Докажите, что возможно определить d(x;y) для произвольных клеток х и у;
2) Вычислите d(с5;g8);
3) Докажите, что для произвольных клеточек x, y и z шахматной доски верно неравенство d(x;y) < d(x;z) + d(z;y)

Вот реальное условие задачи. Только в п.3 неравенство не строгое.
Первый пункт не предполагает формулы, а вот второй? Если вычислить, то наверное по методу (формуле) выведенной в первом пункте

[Cash]

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

Алгоритмически расстояние между двумя клетками можно получить следующим образом. Берем начальную клетку (уровень 0). Отмечаем все клетки на расстоянии одного хода коня. Получаем клетки уровня 1. Повторяем эту процедуру для всех клеток уровня 1 - получаем клетки уровня 2 и т.д., пока все клетки не будут отмечены.

2. Из клетки c5 в клетку g8 можно попасть за $n$ ходов коня. Найдите по возможности наименьшее $n$ и, используя сказанное выше, докажите, что меньшим количеством ходов обойтись нельзя.
3. Проложите маршрут из $x$ в $y$ через $z$.

[Fedya]

Cash в сообщении #612191 писал(а):

Алгоритмически расстояние между двумя клетками можно получить следующим образом. Берем начальную клетку (уровень 0). Отмечаем все клетки на расстоянии одного хода коня. Получаем клетки уровня 1. Повторяем эту процедуру для всех клеток уровня 1 - получаем клетки уровня 2 и т.д., пока все клетки не будут отмечены.

Перечитываю и продумываю все еще раз. Если составить алгоритм для определения наименьшего количества ходов. Задав клеточке а1 координаты (0;0), а2 соответственно (0;1), клеточке b1 - (1;0) и так далее. И начиная с клеточки (0;0) как приведено выше определяем за сколько ходов можно добраться до каждой клеточки. Ходов может быть от одного до шести. Если движение совершать между клеточками разного цвета, то расстояние нечетное, если между клеточками одного цвета, то четное.
Еще введем одно определение, что смещением будем считать произведение разностей соответствующих координат. Определим смещение для клеточек разного цвета:
достижимые за один ход: 2
достижимые за три хода: 0;4;6;10;12;20
достижимые за пять ходов: 0;14;28;42

Теперь для клеточек одинакового цвета
достижимые за 2 хода: 0;3;8;9
достижимые за 4 хода: 0;1;4;5;7;12;15;16;21;24;25;35;36
достижимые за 6 ходов: 49

Заметим, что в первом и втором случаях повторяется только ноль. Для этого введем еще одно определение сумма - сумма координат клеточки (заметим что для черных клеточек она четная, для белых нечетная)

Теперь сам алгоритм:
1) Находим суммы клеточек, начальной и конечной и смещение.
2) Если суммы одинаковой четности, то
достижимые за 2 хода: 0;3;8;9
достижимые за 4 хода: 0;1;4;5;7;12;15;16;21;24;25;35;36
достижимые за 6 ходов: 49

Если разного цвета, то
достижимые за один ход: 2
достижимые за три хода: 0;4;6;10;12;20
достижимые за пять ходов: 0;14;28;42
3) Если смещение равно 0, то рассматриваем сумму конечной точки:
Если 2 или 4, то два хода
Если 1;3 или 5, то три хода
Если 6, то 4 хода
Если 7, то 5 ходов.

-- 29.08.2012, 16:42 --

Вычислите d(с5;g8)
с - 2, g - 6. Следовательно точки (2;4), (6;7)

1) суммы клеточек 6 и 13, следовательно они разного цвета. Смещение (6-2)х(7-4)=12.
2) исходя из этого

разного цвета:
достижимые за один ход: 2
достижимые за три хода: 0;4;6;10;12;20
достижимые за пять ходов: 0;14;28;42

Делаем вывод, что расстояние между клеточками равно 3

-- 29.08.2012, 16:44 --

Уважаемые форумчане, пожалуйста скажите, можно ли что-либо с этого извлечь? Или это бред?

[ИСН]

К турнику привязываем за один конец доску. Это будет минутная стрелка. Вася раскручивает доску, чтобы она делала полный оборот, Петя швыряет в неё гнилыми помидорами, а Вова снимает всё это на видеокамеру. Потом покадровым просмотром находим, под каким углом была доска в момент столкновения с помидором. Так находим время...