Maths Olympiad Prep

Library / /598 of 740

, 2014

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
How many lines pass through exactly two points in the following hexagonal grid?

Figure 1

Solution

Solution:
Answer: 6060

First solution. From a total of 1919 points, there are (192)=171\binom{19}{2} = 171 ways to choose two points. We consider lines that pass through more than 22 points.
- There are 6+6+3=156 + 6 + 3 = 15 lines that pass through exactly three points. These are: the six sides of the largest hexagon, three lines through the center (perpendicular to the sides of the largest hexagon), and the other six lines perpendicular to the sides of the largest hexagon.
- There are 66 lines that pass through exactly four points. (They are parallel to the sides of the largest hexagon.)
- There are 33 lines that pass through exactly five points. (They all pass through the center.)
For each n=3,4,5n = 3, 4, 5, a line that passes through nn points will be counted (n2)\binom{n}{2} times, and so the corresponding amount will have to be subtracted. Hence the answer is
171(32)15(42)6(52)3=171453630=60 171 - \binom{3}{2} \cdot 15 - \binom{4}{2} \cdot 6 - \binom{5}{2} \cdot 3 = 171 - 45 - 36 - 30 = 60

Second solution. We divide the points into 44 groups as follows.
- Group 11 consists of the center point.
- Group 22 consists of the 66 points surrounding the center.
- Group 33 consists of the 66 vertices of the largest hexagon.
- Group 44 consists of the 66 midpoints of the sides of the largest hexagon.
We wish to count the number of lines that pass through exactly 22 points. Consider: all lines connecting points in group 11 and 22, 11 and 33, and 11 and 44 pass through more than 22 points. So it is sufficient to restrict our attention to group 22, 33 and 44.
- For lines connecting group 22 and 22, the only possibilities are those that the two endpoints are 120120 degrees apart with respect to the center, so 66 possibilities.
- For lines connecting group 33 and 33, it is impossible.
- For lines connecting group 44 and 44, the two endpoints must be 6060 degrees apart with respect to the center, so 66 possibilities.
- For lines connecting group 33 and 22. For each point in group 33, the only possible points in group 22 are those that are 120120 degrees apart from the point in group 33. So 26=122 \cdot 6 = 12 possibilities.
- For lines connecting group 44 and 22, the endpoints must be 150150 degrees apart with respect to the center, so 26=122 \cdot 6 = 12 possibilities.
- For lines connecting group 44 and 33. For each point in group 44, any point in group 33 works except those that are on the side on the largest hexagon of which the point in group 44 is the midpoint. Hence 46=244 \cdot 6 = 24 possibilities.
Therefore, the number of lines passing through 22 points is 6+6+12+12+24=606 + 6 + 12 + 12 + 24 = 60, as desired.

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.