Skip to main content
1 of 6
Paul Sinclair
  • 1.3k
  • 7
  • 15

Some thoughts: call the occurrence of a tree in a row an "instance". There are 30 instances total (3 on each row). Call the number of instances of a particular tree its "degree". Then the average degree of the trees is ${30\over9} = 3{1\over3}$. So at least some of the trees have degree 4 or higher. However, if a tree has degree $n$, then there are $2n$ other instances on rows containing the tree. The two instances on any given row have to be unique so that the row will have 3 trees, and if any two of the rows share the same other tree, then those rows (lines) have two trees (points) in common, meaning that they are not distinct rows. Therefore all $2n$ instances have to be of distinct trees. As there are only $8$ other trees, this puts a maximum on $n$ of $4$.

Note that for any degree-4 tree, every other tree shares a row with it. This means that every non-degree-4 tree is in at least as many rows as half the number of degree 4-trees. I.e., there can be no more degree-4 trees than twice the lowest degree of any tree.

Now how many trees can there be of each degree? Let $d_n$ be the number of trees of degree $n$. The number of instances is the sum of the degrees of all the trees, so we can express it as:$$\begin{align}30 &= 4d_4 + 3d_3 + 2d_2 + d_1\\&= 4(9 - d_3 - d_2 - d_1) + 3d_3 + 2d_2 + d_1\\6 &= d_3+2d_2+3d_1\end{align}$$ (where I am assuming every tree is on at least one row). Hence we can have no more than $6$ trees of degree < 4, and must have at least 3 degree-4 trees. But since the number of degree 4 trees has to be at most twice the lowest degree, there can be no degree-1 trees. So $6 = d_3 + 2d_2$, and we have four cases:

  • $d_2 = 0, d_3 = 6, d_4 = 3$. This is the case for both examples that have been found at the time of this post.
  • $d_2 = 1, d_3 = 4, d_4 = 4$.
  • $d_2 = 2, d_3 = 2, d_4 = 5$, but since $d_2 > 0$, we must have $d_4 \le 2(2) = 4$, so this cannot be.
  • $d_2 = 3, d_3 = 0, d_4 = 6$, but again this has more degree-4 trees than can be supported.

Therefore any solutions must either have $3$ trees lying on $4$ rows and $6$ trees lying on $3$ rows, or else have $4$ trees lying on $4$ rows, $4$ trees lying on $3$ rows and $1$ tree that is only in $2$ rows.

Paul Sinclair
  • 1.3k
  • 7
  • 15