Азиатско-Тихоокеанская математическая олимпиада, 2011 год

Пусть $n$ — фиксированное положительное нечетное число. Рассмотрим $m+2$ различные точки $P_0, P_1, \dots, P_{m+1}$ на координатной плоскости, которые удовлетворяют следующим трем условиям (здесь $m$ — неотрицательное целое число):
(1) $P_0 = (0,1)$, $P_{m+1} = (n+1, n)$, и для каждого $1 \le i \le m$, обе $x-$ и $y-$ координаты точки $P_i$ — целые числа, лежащие в интервале $[1,n]$.
(2) Для каждого $0 \le i \le m$ прямая $P_{i}P_{i+1}$ параллельна оси $Ox$ при четном $i$, и параллельна оси $Oy$ при нечетном $i$.
(3) Для каждой пары $0 \le i < j \le m$ отрезки $P_{i}P_{i+1}$ и $P_{j}P_{j+1}$ имеют не более одной общей точки.
Определите наибольшее возможное значение, которое может принимать число $m$.

Комментарий/решение

Мы утверждаем, что $m \leq n^2 -n$.

Во-первых, в каждом столбце не более $n-1$ точек, исключая первый и последний столбцы, так как каждая точка должна быть в паре с другой внутри того же столбца. Обратите внимание, что этот же подход не работает, если вы рассматриваете точки в строках, поскольку первый сегмент $P_0P_1$ горизонтален, а последний сегмент $P_mP_{m+1}$ горизонтален, поэтому вы можете получить только $m \leq n^2. - н +2$