AoPS - Problem

Source: Central American Olympiad 2001, problem 6

Tags: modular arithmetic

tonypr

12.08.2009 05:14

In a circumference of a circle, $ 10000$ points are marked, and they are numbered from $ 1$ to $ 10000$ in a clockwise manner. $ 5000$ segments are drawn in such a way so that the following conditions are met: 1. Each segment joins two marked points. 2. Each marked point belongs to one and only one segment. 3. Each segment intersects exactly one of the remaining segments. 4. A number is assigned to each segment that is the product of the number assigned to each end point of the segment. Let $ S$ be the sum of the products assigned to all the segments. Show that $ S$ is a multiple of $ 4$.

Umm? .. take any pair of intersecting lines with vertices $ a,b,c,d$ in clockwise order, because they do not intersect any other lines the number of points between $ a$ and $ b$ is divisible by $ 4$ and so forth. Then $ b,d \equiv a,c \pm 1 \pmod{4}$, eg even numbers will be paired with even numbers and odd number with odds. The product of the even numbers has no effect on $ S$ $ \mod 4$, and the odd numbers can be partitioned into two sets of $ 2500$ elements leaving residues of $ 1$ and $ 3$ respectively $ \mod 4$. Trivially we find that the sum of the products of pairs of elements from these sets will be divisible by $ 4$ ..