На доске шахматной

[daogiauvang]

На шахматной доске размера $n \times n, n \geq 3$ расставлены $n$ ладей в центрах клеток так, чтобы никакие две ладьи друг другу не угрожали. Доказать, что среди расстояний между ладьями существует два равных расстояния.

[Aritaborian]

(ТеХническое)

\times: $n \times n$.

[Karan]

daogiauvang, по-видимому, Вы не очень хорошо владеете русским языком и условие задачи в Вашем сообщении трудно понять. Я перемещу тему в Карантин, где Вы можете исправить формулировку задачи. Вы также можете написать условие задачи на английском языке.
It seems that you don't know Russian well enough, so your problem description is hard to understand. I'm moving the topic to the Quarantine forum where you can fix the problem description, possibly rewriting it in English.

Исправьте Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Fix your errors and leave a message for the moderators in the topic Сообщение в карантине исправлено

[Karan]

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»

[worm2]

Для $n\geqslant 8$ особенно просто доказывается.
Например, при $n=8$ различных пар ладей — 28, а возможных расстояний между ними — 27 ($1^2+7^2=5^2+5^2$).

-- Ср авг 16, 2017 15:09:28 --

Хотя общий случай не намного сложнее.
Если самая левая ладья стоит на $i$-й горизонтали, а самая правая — на $j$-й, то расстояние $\sqrt{x^2+(n-1)^2}$ реализуется только для одного $x=|i-j|$, а для остальных $x$ оно выпадает из числа возможных. Таким образом, число возможных разрешённых расстояний между клетками получается меньше, чем число возможных расстояний между ладьями $n(n-1)/2$.
Это рассуждение грешит неточностями, до строгого доказательства лень доводить.

[daogiauvang]

worm2 в сообщении #1241053 писал(а):

а для остальных $x$ оно выпадает из числа возможных. Таким образом, число возможных разрешённых расстояний между клетками получается меньше, чем число возможных расстояний между ладьями $n(n-1)/2$.
Это рассуждение грешит неточностями, до строгого доказательства лень доводить.

Это не очень понятно!!!

[DeBill]

Если все расстояния различны, то каждое возможное встретится ровно 1 раз.
Значить, есть максимальное, т.е., пара ладей - в углах. Выкинем их: индукция (база: $n=1,2$ )

[g______d]

Ну кстати асимптотически это верно с запасом: если бы все расстояния были различны, то среди чисел $\{1,\ldots, 2n^2\}$ было бы $\frac{n(n+1)}{2}$ представимых в виде суммы квадратов, а на самом деле их не больше $\frac{C n^2}{\log n}$.

http://mathworld.wolfram.com/Landau-Ram ... stant.html