Азия-тынық мұхит математикалық олимпиадасы, 2011 жыл
n бекітілген оң, тақ бүтін сан болсын. Координаттар жазықтығынан алынған әртүрлі m+2 нүкте (мұндағы m -- теріс емес, бүтін сан) — P0,P1,…,Pm+1 — төмендегі үш шартты қанағаттандырады:
(1) P0=(0,1), Pm+1=(n+1,n) және әрбір 1≤i≤m үшін Pi нүктесінің x− пен y− координаттарының екеуі де [1,n] интервалында жатқан бүтін сандар болады.
(2) Әрбір 0≤i≤m үшін PiPi+1 түзуі, егер i жұп болса, Ox өсіне параллель, ал, егер i тақ болса, Oy өсіне параллель болады.
(3) Әрбір 0≤i<j≤m пары үшін PiPi+1 и PjPj+1 кесінділерінің, ең көп дегенде, бір ғана ортақ нүктесі табылады. m санының ең үлкен мүмкін мәнін анықтаңдар.
посмотреть в олимпиаде
(1) P0=(0,1), Pm+1=(n+1,n) және әрбір 1≤i≤m үшін Pi нүктесінің x− пен y− координаттарының екеуі де [1,n] интервалында жатқан бүтін сандар болады.
(2) Әрбір 0≤i≤m үшін PiPi+1 түзуі, егер i жұп болса, Ox өсіне параллель, ал, егер i тақ болса, Oy өсіне параллель болады.
(3) Әрбір 0≤i<j≤m пары үшін PiPi+1 и PjPj+1 кесінділерінің, ең көп дегенде, бір ғана ортақ нүктесі табылады. m санының ең үлкен мүмкін мәнін анықтаңдар.
Комментарий/решение:
Мы утверждаем, что m≤n2−n.
Во-первых, в каждом столбце не более n−1 точек, исключая первый и последний столбцы, так как каждая точка должна быть в паре с другой внутри того же столбца. Обратите внимание, что этот же подход не работает, если вы рассматриваете точки в строках, поскольку первый сегмент P0P1 горизонтален, а последний сегмент PmPm+1 горизонтален, поэтому вы можете получить только m≤n2.−н+2
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.