Азия-тынық мұхит математикалық олимпиадасы, 2011 жыл

$n$ бекітілген оң, тақ бүтін сан болсын. Координаттар жазықтығынан алынған әртүрлі $m+2$ нүкте (мұндағы $m$ -- теріс емес, бүтін сан) — $P_0, P_1, \dots, P_{m+1}$ — төмендегі үш шартты қанағаттандырады:
(1) $P_0 = (0,1)$, $P_{m+1} = (n+1, n)$ және әрбір $1 \le i \le m$ үшін $P_i$ нүктесінің $x-$ пен $y-$ координаттарының екеуі де $[1,n]$ интервалында жатқан бүтін сандар болады.
(2) Әрбір $0 \le i \le m$ үшін $P_{i}P_{i+1}$ түзуі, егер $i$ жұп болса, $Ox$ өсіне параллель, ал, егер $i$ тақ болса, $Oy$ өсіне параллель болады.
(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$