Tom was given a total of $9$ candies plus an infinite number of lines and he need to place them such that it follows the following condition:
1) when connecting two candies with a line, there must be three candies on that line or we cannot place it;
2) a candy can be on different lines
Show the maximum number of lines that can be created following this rule. An image is provided below for having 5 points:
This is an extension problem from the KSEA 2018 grade 11 math exam (a finished math contest held on 4/7) , and I really struggled with this. First of all I started with small examples:
$3$ candy- $1$ lines
$4$ candy- $1$ line
$5$ candy- $2$ lines
$6$ candy- $4$ lines
Although I am pretty sure about these examples, I am really shaky to advance; I do not have a systematic method. One of my ideas is to argue by combinatorics; for each line generated, there will be a total of $3 \choose 2$ ways to connect two candies taken away. Then I tried this to disprove that 5 candies can generate 3 lines; but $5 \choose 2$- 3$3 \choose 2$ is not negative which shows my way doesnt work... I cannot really come up with a proper solution for this. Some suggestion will be greatly appreciated.
The maximum number of lines $\mathcal{N}$ is $10$.
This number $10$ is achieved by following configuration:
This bounds $\mathcal{N}$ from below by $10$.
For an upper bound, let $S \subset \mathbb{R}^2$ be any set of $n \ge 3$ points in the plane and $L$ be the collection of lines containing at least 2 points from $S$.
Out of these $n$ points, we can form $\frac12 n(n-1)$ pairs from them. For any line in $L$, if it contains $m$ points from $S$, it will contain $\frac12 m(m-1)$ pairs. Notice a pair uniquely determine a line, this means the set of pairs associated with different lines in $L$ are disjoint. If we let $N_m$ be the number of lines containing $m$ points from $S$, we have:
$$\frac{n(n-1)}{2} = \sum_{m \ge 2} N_m \frac{m(m-1)}{2}\tag{*1}$$
This leads to $\quad\displaystyle\frac{n(n-1)}{2} \ge N_2 + 3 N_{\ge 3}\quad$ where $\quad N_{\ge 3} \stackrel{def}{=} \sum\limits_{m\ge 3} N_m$.
In $1958$, Kelly and Moser has shown$\color{blue}{{}^{[1]}}$:
For the problem at hand, we have $n = 9$. Above result implies
$$N_{\ge 3} \le \frac13 \left(\frac{9(9-1)}{2} - \frac{3(9)}{7}\right) = \frac{75}{7}$$ Since LHS is an integer, we find $N_{\ge 3} \le 10$ unless $S$ lies on a single line. If $S$ lies on a single line, it is clear $N_{\ge 3} = 1$. Combine these, we can conclude out of any set $S$ of $9$ points, we can construct at most $10$ lines which passes through $3$ or more points from $S$.
This establishes the upper bound $\mathcal{N} \le 10$. Combine with the lower bound, we conclude $\mathcal{N} = 10$.
The problem here is related to the orchard-planting problem which asks how to plant $n$ trees so that there will be $r(n,k)$ straight rows with k trees in each row. The variant of finding the maximum number of $3$-point lines for $n$ points is due to Sylvester. Look at Borwein and Moser's survey article$\color{blue}{{}^{[2]}}$ for more info about the Sylvester problem. In particular, it has a proof of the Kelly and Moser's result mentioned above.
Notes/References
$\color{blue}{[1]}$ - Kelly, L.M. and Moser, W. 1958. On the number of ordinary lines determined by $n$ points. Canad. J. Math. 10, 210-219. MR: 20, #3494.
$\color{blue}{[2]}$ - Borwein, P & O. J. Moser, W. (1990). A survey of Sylvester's problem and its generalizations. Aequationes Mathematicae. 40. 111-135. 10.1007/BF02112289.