Maths Olympiad Prep

Library / /14 of 17

Geometry Difficulty 6.5 National Olympiad Prove it Ukraine

In the plane, 20052005 points were marked, no three of which are collinear. Straight lines were drawn through all the pairs of marked points. Prove that all the marked points can be colored into two colors in such a way that for any two points of the same color the number of the drawn lines separating them is even. (We say that a line separates two points if none of those points belongs to it, and they lie in different half-planes with respect to it.)

Solution

Крім того, покладемо
δ(a,P,Q,R)=δ(a,P,Q)+δ(a,Q,R)+δ(a,P,R). \delta(a,P,Q,R) = \delta(a,P,Q) + \delta(a,Q,R) + \delta(a,P,R).
Розглянемо довільні три відмічені точки PP, QQ, RR. Очевидно, що
nPQ+nQR+nPR=aδ(a,P,Q,R), n_{PQ} + n_{QR} + n_{PR} = \sum_{a} \delta(a,P,Q,R),
де сума береться по всіх проведених прямих.
Легко бачити, що якщо пряма aa проходить через дві з точок PP, QQ, RR, то маємо рівність δ(a,P,Q,R)=0\delta(a,P,Q,R)=0. Якщо пряма aa проходить рівно через одну з них, то δ(a,P,Q,R){0;1}\delta(a,P,Q,R) \in \{0;1\}. А якщо пряма aa не проходить через жодну, то маємо, що δ(a,P,Q,R){0;2}\delta(a,P,Q,R) \in \{0;2\}.
Розглянувши всі сім усіляких випадків взаємного розташування чотирьох точок на площині, одержуємо, що для будь-якої точки XX з решти 20022002 відмічених точок або серед трьох прямих XPXP, XQXQ, XRXR тільки одна розділяє дві точки з числа точок PP, QQ, RR, або ж кожна з прямих XPXP, XQXQ, XRXR має таку властивість. Отже, парність числа nPQ+nQR+nPRn_{PQ} + n_{QR} + n_{PR} визначається кількістю зазначених вище точок XX, а їх саме C20021=2002C_{2002}^1 = 2002. Таким чином, ми довели, що число nPQ+nQR+nPRn_{PQ} + n_{QR} + n_{PR} є парним для будь-яких трьох відмічених точок PP, QQ, RR. А тому серед чисел nPQn_{PQ}, nQRn_{QR}, nPRn_{PR} парними є або всі три, або ж — тільки одне. З цього випливає, що якщо для якоїсь точки PP пофарбувати всі ті точки QQ, для яких nPQn_{PQ} парне, у той самий колір, що й точку PP, а решту точок — у другий колір, то таке розфарбування буде задовольняти умову.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.