2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Задача про коня на клетчатой плоскости.
Сообщение17.07.2015, 13:37 


04/06/13
203
Здравствуйте! Подскажите, пожалуйста, идею, как упростить перебор вариантов?

На клетчатой плоскости отмечено несколько клеток. На каждой клетке плоскости написано, за какое наименьшее число ходов шахматный конь может дойти от этой клетки до какой-нибудь отмеченной. Андрей вырезал из плоскости полоску
$5\times 1$, не содержащую отмеченных клеток. Докажите, что в клетках этой полоски есть два равных числа.

Первое, что я сделал -- это взял отмеченную точку и начал заполнять плоскость числами.

Изображение

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

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение17.07.2015, 13:49 
Заслуженный участник
Аватара пользователя


09/09/14
6104
karandash_oleg в сообщении #1038031 писал(а):
Первое, что я сделал -- это взял отмеченную точку и начал заполнять плоскость числами.

Надо было начать с другого -- разобраться, как ходит конь :D Я ещё не вникал, но первая же клетка, которую я проверил, была ошибочная (в соседней по диагонали от выделенной должно быть 2, а не 3).

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение17.07.2015, 13:55 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Ну вот стоит у вас конь в какой-нибудь клетке, и пусть в этой клетке записано число $n>0.$ Значит найдётся хотя бы одна клетка на которую конь может перейти за один ход и в которой записано число $n-1.$ А сколькими способами он может вернуться на прежнюю линию? И не забудьте, что отмеченных клеток несколько (то есть больше одной).

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение17.07.2015, 14:00 
Заслуженный участник
Аватара пользователя


23/08/07
4732
Нов-ск
karandash_oleg в сообщении #1038031 писал(а):
Как можно учесть все эти нюансы.
Внутри полоски из любой клетки в любую нужно не более трех ходов. Поэтому в полоске не могут быть разные числа (ведь среди них были бы отличные минимум на 4)

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение18.07.2015, 10:40 


04/06/13
203
whitefox в сообщении #1038039 писал(а):
Ну вот стоит у вас конь в какой-нибудь клетке, и пусть в этой клетке записано число $n>0.$ Значит найдётся хотя бы одна клетка на которую конь может перейти за один ход и в которой записано число $n-1.$ А сколькими способами он может вернуться на прежнюю линию? И не забудьте, что отмеченных клеток несколько (то есть больше одной).

В такой ситуации -- один способ из клетки с номером $1$.

Изображение

Но можно зациклить, увеличить путь до миллиона способов, гуляя по шахматной доске, наворачивая круги.

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение18.07.2015, 15:22 
Заслуженный участник
Аватара пользователя


19/12/10
1539
А вы рассмотрите не клетку с числом 2, а клетку слева от неё. Впрочем, это уже не важно — TOTAL дал полное решение. :-)

 Профиль  
                  
 
 Re: Задача про коня на клетчатой плоскости.
Сообщение19.07.2015, 14:25 


04/06/13
203
Спасибо, TOTAL, решение просто шикарно и лаконично)))

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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