Maths Olympiad Prep

Library / /167 of 196

Combinatorics Difficulty 6.0 National Olympiad Prove it Soviet Union

Problem:

nn points lie in the plane, not all on a single line. A real number is assigned to each point. The sum of the numbers is zero for all the points lying on any line. Show that all the assigned numbers must be zero.

Solution

Solution:

Suppose the points are P1,P2,,PnP_1, P_2, \ldots, P_n, and the real numbers assigned are a1,a2,,ana_1, a_2, \ldots, a_n.

Let LL be any line containing some of the points. By hypothesis, the sum of the aia_i for all PiP_i on LL is zero.

Let us show that all ai=0a_i = 0.

Pick three non-collinear points P1,P2,P3P_1, P_2, P_3 (possible since not all points are collinear).

Consider the lines P1P2P_1P_2, P2P3P_2P_3, P3P1P_3P_1.

- On line P1P2P_1P_2, the sum of the aia_i for all points on this line is zero. In particular, a1+a2+aj=0a_1 + a_2 + \sum a_j = 0, where the sum is over all jj such that PjP_j lies on P1P2P_1P_2 (excluding P1P_1 and P2P_2 if no other points).
- Similarly for the other two lines.

Now, consider any point PkP_k not on P1P2P_1P_2. The line P1PkP_1P_k contains P1P_1 and PkP_k (and possibly other points). The sum of the aia_i on this line is zero. Similarly for P2PkP_2P_k.

Let SS be the set of all points. For each line \ell determined by two points, the sum of aia_i over all PiP_i on \ell is zero.

Let AA be the vector (a1,a2,,an)(a_1, a_2, \ldots, a_n). For each line \ell containing mm points, we have a linear equation: i:Piai=0\sum_{i: P_i \in \ell} a_i = 0.

The set of all such equations forms a homogeneous system. Since not all points are collinear, there are at least three non-collinear points, so the configuration is not degenerate.

Suppose some ak0a_k \neq 0. Consider the line through PkP_k and any other point PjP_j. The sum of aia_i on this line is zero, so ak+aj+ai=0a_k + a_j + \sum a_{i'} = 0, where the sum is over all other points on the line. But by varying jj, and using the fact that the configuration is not all collinear, we can show that all ai=0a_i = 0.

Alternatively, consider the following:

Let ff be the function assigning aia_i to PiP_i. For any line \ell, Pif(Pi)=0\sum_{P_i \in \ell} f(P_i) = 0.

Suppose ff is not identically zero. Let PP be a point with f(P)0f(P) \neq 0. Consider all lines through PP. For each such line, the sum of ff over all points on the line is zero, so f(P)=QP,Qf(Q)f(P) = -\sum_{Q \neq P, Q \in \ell} f(Q). Summing over all lines through PP, and using the fact that the configuration is not all collinear, we get a contradiction unless f(P)=0f(P) = 0.

Therefore, all ai=0a_i = 0.

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.