2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Целые числа на шахматной доске
Сообщение10.10.2017, 10:18 
Аватара пользователя


01/12/11

8634
В каждое из полей шахматной доски вписали по целому числу, причём оказалось, что числа, вписанные в поля с общей стороной, отличаются либо на 1, либо на 2. Какое наибольшее количество попарно различных чисел могло быть вписано?
Обобщите задачу на квадратную доску произвольного размера, а также на прямоугольную доску произвольноых размеров.

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


18/05/06
13435
с Территории
Каждый квадратик $2\times2$ представляет собой картинку либо $\begin{array}{c|c}0&1\\\hline1&2\end{array}+\rm const$, либо $\begin{array}{c|c}0&1\\\hline1&0\end{array}+\rm const$. Первое - это наклонная плоскость по диагонали доски, а второе - перегиб на ней. Перегибы нам явно не добавят значений, значит, их и не надо.

 Профиль  
                  
 
 Re: Целые числа на шахматной доске
Сообщение10.10.2017, 11:30 


15/03/11
137
ИСН в сообщении #1254429 писал(а):
Каждый квадратик $2\times2$ представляет собой картинку либо $\begin{array}{c|c}0&1\\\hline1&2\end{array}+\rm const$, либо $\begin{array}{c|c}0&1\\\hline1&0\end{array}+\rm const$.


А почему не $\begin{array}{c|c}0&1\\\hline2&3\end{array}+\rm const$ например?

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


18/05/06
13435
с Территории
А, там по стороне... Тьфу, чёрт, тогда вещи становятся волосатыми.

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


01/08/06
3046
Уфа
Без ограничения общности можно считать, что минимальное число — 0.
Также без ограничения общности можно считать, что остальные числа — кусок натурального ряда, без разрывов. А почему? А потому что если у нас есть разрыв, то числа разбиваются на 2 части: меньшие разрывного, и большие. Уменьшив большие на величину разрыва, мы сохраним число различных чисел, и не увеличим разницу между соседними числами.
Будем понимать под шагом переход на соседнюю клетку по горизонтали или вертикали, а под путём — последовательность шагов.
На обычной доске 8x8 между любыми клетками существует путь длиной не более 14. Значит, максимальное значение может быть не больше 28.
Пусть в какой-то клетке записано 28. Очевидно, она должна находиться в одном из углов, а в противоположном должен быть нуль. Поразмыслив ещё немного, приходим к выводу, что, в силу экстремальности числа 28, вся расстановка однозначно определяется, и у нас получилось разместить всего 15 чисел (чётных). Красиво, но мало.
Попробуем-ка мы разместить 28 различных чисел от 0 до 27.
Пробуем... пробуем.... а не получается.
А почему?
Ну давайте предположим, что это у нас руки кривые, а так-то должно было получиться. Понятно, что 0 и 27 по-прежнему в противоположных углах. Протянем между ними диагональ. Числа на диагонали, в силу околоэкстремальности числа 27, имеют весьма мало пространства для манёвра. А именно, между соседними клетками этой диагонали одна разность чисел равна 3, а остальные шесть равны 4 (иначе одна из разностей была бы больше 4, что, очевидно, невозможно). Нас интересует та пара смежных клеток диагонали, числа в которых отличаются на 3. Через общую точку этой пары клеток проведём горизонтальную и вертикальную прямые, которые делят доску на 4 части: два квадрата (в одном из которых 0, в противоположном 27) и два прямоугольника.
Числа внутри квадратов определяются однозначно. Это ключевое утверждение, без хорошего понимания которого в дальнейших рассуждениях невозможно разобраться.
В "нулевом" квадрате — только чётные числа, в противоположном — только нечётные. Где-то в двух оставшихся прямоугольниках мы должны разместить числа 1 и 26 (которых внутри квадратов нет). А не получится! Потому что 1 должен быть недалеко от нуля, но тогда "нулевой" квадрат должен быть размерами не более 2x2, но тогда противоположный квадрат — размерами не менее 6x6, и вне него мы не можем разместить 26, т.к. легко посчитать, что максимальное число вдоль той границы квадрата, рядом с которой мы можем размещать числа — не более 17.

Итак, больше 27 различных чисел мы разместить не сможем. А 27 — запросто. Это совсем не сложно, но что-то мне лень таблицу рисовать... Например, так: в одном углу квадрат 2x2 (сверху строка (0, 2), снизу строка (1, 3)), в противоположном — квадрат ((23, 24), (25, 26)), на диагонали между 3 и 23 внутренний квадрат 6x6 определяется однозначно, он заполнен регулярным образом нечётными числами. Остаются незадействованными чётные от 4 до 22, которые легко размещаются на оставшихся полосках: горизонтальной 4..12, в углу 13, и вертикальной 14..22. Божечки, как же ж мне лень таблицу рисовать... Там ещё нужно показать, что в оставшихся полосках числа размещаются без проблем.

 Профиль  
                  
 
 Re: Целые числа на шахматной доске
Сообщение11.10.2017, 16:41 
Аватара пользователя


01/12/11

8634
worm2
Большое спасибо!

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

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



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

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


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

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