Maths Olympiad Prep

Library / /440 of 520

Combinatorics Difficulty 3.9 AMC 10/12 Find the answer

Lines L1,L2,,L100L_1,L_2,\dots,L_{100} are distinct. All lines L4n,nL_{4n}, n a positive integer, are parallel to each other.
All lines L4n3,nL_{4n-3}, n a positive integer, pass through a given point A.A. The maximum number of points of intersection of pairs of lines from the complete set {L1,L2,,L100}\{L_1,L_2,\dots,L_{100}\} is

Pick one

Solution

We partition {L1,L2,,L100}\{L_1,L_2,\dots,L_{100}\} into three sets. Let
X={Lnn0(mod4)},Y={Lnn1(mod4)},Z={Lnn2,3(mod4)},\begin{align*} X &= \{L_n\mid n\equiv0\pmod{4}\}, \\ Y &= \{L_n\mid n\equiv1\pmod{4}\}, \\ Z &= \{L_n\mid n\equiv2,3\pmod{4}\}, \\ \end{align*}
from which X=Y=25|X|=|Y|=25 and Z=50.|Z|=50.
Any two distinct lines can intersect at most once. To maximize the number of points of intersection, note that each point must be passed by exactly two lines. If three or more lines pass through the same point, then we can create more points of intersection by translating the lines.
We construct the sets one by one:

We construct all lines in set X.X.
Since the lines in set XX are parallel to each other, they have 00 points of intersection.

We construct all lines in set Y.Y.
The lines in set YY have 11 point of intersection with each other, namely A.A.
Moreover, each line in set YY can intersect each line in set XX once. So, there are 252=62525^2=625 points of intersection.
Now, we have 1+625=626\boldsymbol{1+625=626} additional points of intersection.

We construct all lines in set Z.Z.
The lines in set ZZ can have (502)=1225\binom{50}{2}=1225 points of intersection with each other.
Moreover, each line in set ZZ can intersect each line in sets XX and YY once. So, there are 502=250050^2=2500 points of intersection.
Now, we have 1225+2500=3725\boldsymbol{1225+2500=3725} additional points of intersection.

Together, the answer is 626+3725=(B) 4351.626+3725=\boxed{\textbf{(B) }4351}.
~MRENTHUSIASM

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.