Maths Olympiad Prep

Library / /314 of 348

Combinatorics Difficulty 5.2 AIME, harder Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

First solution. From a total of 19 points, there are (192)=171\binom{19}{2}=171 ways to choose two points. We consider lines that pass through more than 2 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 perpendiculars to the sides of the largest hexagon. - There are 6 lines that pass through exactly four points. (They are parallel to the sides of the largest hexagon.) - There are 3 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=60171-\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 4 groups as follows. - Group 1 consists of the center point. - Group 2 consists of the 6 points surrounding the center. - Group 3 consists of the 6 vertices of the largest hexagon. - Group 4 consists of the 6 midpoints of the sides of the largest hexagon. We wish to count the number of lines that pass through exactly 2 points. Consider: all lines connecting points in group 1 and 2,1 and 3, and 1 and 4 pass through more than 2 points. So it is sufficient to restrict our attention to group 2,3 and 4. - For lines connecting group 2 and 2, the only possibilities are those that the two endpoints are 120 degrees apart with respect to the center, so 6 possibilities. - For lines connecting group 3 and 3, it is impossible. - For lines connecting group 4 and 4, the two endpoints must be 60 degrees apart with respect to the center, so 6 possibilities. - For lines connecting group 3 and 2. For each point in group 3, the only possible points in group 2 are those that are 120 degrees apart from the point in group 3. So 26=122 \cdot 6=12 possibilities. - For lines connecting group 4 and 2, the endpoints must be 150 degrees apart with respect to the center, so 26=122 \cdot 6=12 possibilities. - For lines connecting group 4 and 3. For each point in group 4, any point in group 3 works except those that are on the side on the largest hexagon of which the point in group 4 is the midpoint. Hence 46=244 \cdot 6=24 possibilities. Therefore, the number of lines passing through 2 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.