Loading [MathJax]/jax/output/SVG/jax.js

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


n бекітілген оң, тақ бүтін сан болсын. Координаттар жазықтығынан алынған әртүрлі m+2 нүкте (мұндағы m -- теріс емес, бүтін сан) — P0,P1,,Pm+1 — төмендегі үш шартты қанағаттандырады:
(1) P0=(0,1), Pm+1=(n+1,n) және әрбір 1im үшін Pi нүктесінің x пен y координаттарының екеуі де [1,n] интервалында жатқан бүтін сандар болады.
(2) Әрбір 0im үшін PiPi+1 түзуі, егер i жұп болса, Ox өсіне параллель, ал, егер i тақ болса, Oy өсіне параллель болады.
(3) Әрбір 0i<jm пары үшін PiPi+1 и PjPj+1 кесінділерінің, ең көп дегенде, бір ғана ортақ нүктесі табылады. m санының ең үлкен мүмкін мәнін анықтаңдар.
посмотреть в олимпиаде

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

  5
1 года 4 месяца назад #

Мы утверждаем, что mn2n.

Во-первых, в каждом столбце не более n1 точек, исключая первый и последний столбцы, так как каждая точка должна быть в паре с другой внутри того же столбца. Обратите внимание, что этот же подход не работает, если вы рассматриваете точки в строках, поскольку первый сегмент P0P1 горизонтален, а последний сегмент PmPm+1 горизонтален, поэтому вы можете получить только mn2.н+2