Maths Olympiad Prep

Library / /103 of 104

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Bulgaria

Problem:
Find all positive integers nn for which there exists nn points in the plane such that any of them lies on exactly 13\frac{1}{3} of the lines determined by these nn points.

Solution

Solution:
We shall prove that n=6n=6. If we take 6 points in general position (no three are collinear), then the lines are 15 and any point lies on 5 lines, i.e. n=6n=6 is a solution of the problem.

Denote by kk the number of the lines defined by the given nn points. Assume that there is a line ll containing 4 of the given points. Any of the points belongs to k31\frac{k}{3}-1 lines different from ll which means that there are at least 4(k31)+14\left(\frac{k}{3}-1\right)+1 lines. Then
4(k31)+1k 4\left(\frac{k}{3}-1\right)+1 \leq k
i.e., k9k \leq 9. On the other hand, any point lying not on ll belongs to at least four lines (the lines through the point and the four points on ll) and hence k12k \geq 12, a contradiction. So any line contains at most 3 points. Let aa of the lines contain 2 points. Then each of the other kak-a lines contains 3 points.

The number of the points (any of them counted k3\frac{k}{3} times) is equal to 2a+3(ka)2a + 3(k-a) and then 2a+3(ka)=nk32a + 3(k-a) = \frac{nk}{3}. On the other hand, since nn points define n(n1)2\frac{n(n-1)}{2} lines (some of them may coincide) and any line containing three points is counted three times, then a+3(ka)=n(n1)2a + 3(k-a) = \frac{n(n-1)}{2}. Thus
a=n(n1)(9n)2(2n9),k=3n(n1)2(2n9) a = \frac{n(n-1)(9-n)}{2(2n-9)}, \quad k = \frac{3n(n-1)}{2(2n-9)}
Since kn(n1)2k \leq \frac{n(n-1)}{2}, then 2n932n-9 \geq 3, i.e., n6n \geq 6. Now a0a \geq 0 implies that n9n \leq 9. For n=7n=7 the values of aa and kk are not integers and hence n=8n=8 or n=9n=9. For n=8n=8 one has that k=12,a=4k=12, a=4 and for n=9n=9 we get that k=12,a=0k=12, a=0.

Denote by ll the maximal number of points in general position among the given nn points. Then the remaining points belong to lines defined by these ll points.

Case 1. Let l=3l=3 and let the respective points be A1,A2,A3A_{1}, A_{2}, A_{3}. Any of the other points lies on one of the lines A1A2,A1A3A_{1}A_{2}, A_{1}A_{3} and A2A3A_{2}A_{3}. Since any line contains at most 3 points, then we have at most 6 points, a contradiction.

Case 2. Let l=4l=4 and let the respective points be A1,A2,A3,A4A_{1}, A_{2}, A_{3}, A_{4}. Since the total number of the points is at least 8, we may find a point belonging to exactly one of the lines defined by A1,A2,A3,A4A_{1}, A_{2}, A_{3}, A_{4}. We may assume that the point is A5A_{5} and A5A1A2A_{5} \in A_{1}A_{2}. Then the points A3,A4,A1,A5A_{3}, A_{4}, A_{1}, A_{5} as well as A3,A4,A2,A5A_{3}, A_{4}, A_{2}, A_{5} are in general position. Hence all the points must belong to the lines defined by A1,A2,A3,A4;A3,A4,A1,A5A_{1}, A_{2}, A_{3}, A_{4}; A_{3}, A_{4}, A_{1}, A_{5} and A3,A4,A2,A5A_{3}, A_{4}, A_{2}, A_{5}. The only common lines are A3A4A_{3}A_{4} and A1A2A5A_{1}A_{2}A_{5}, i.e., all the points lie on two lines. This is a contradiction to the fact that any line contains at most 3 points.

Case 3. Let l=5l=5 and let the respective points be A1,A2,A3,A4,A5A_{1}, A_{2}, A_{3}, A_{4}, A_{5}. Any of the points A1,A2,A3,A4,A5A_{1}, A_{2}, A_{3}, A_{4}, A_{5} belongs to exactly 4 lines. This means that A6Ai,i=1,2,,5A_{6}A_{i}, i=1,2, \ldots, 5, is one of these lines. We may assume that A6A1A2A_{6} \in A_{1}A_{2}. Then A6A3A_{6}A_{3} is one of the lines A3A4,A3A5A_{3}A_{4}, A_{3}A_{5} or A4A5A_{4}A_{5}. Let us have, for example, A6A3A4A_{6} \in A_{3}A_{4}. Then A6A5A_{6}A_{5} is a new line, a contradiction.

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.