Return to Answer

Let $d_n$ be the number of trees of degree $n$. By the lemma $n \le 4$. Then the number of instances (30) is the sum of the degrees for all trees, which is $$ 30 = 4d_4 + 3d_3 + 2d_2 + 1d_1$$ but $$9 = d_4 + d_3 + d_2 + d_1$$ Eliminating $d_4$ gives $$ 6 = d_3 + 2d_2 + 3d_1$$ So the total number of trees of degree $< 4$ is at most $6$, leaving at least $3$ 4-trees. By the lemma, the smallest degree possible is therefore $2$, so $d_1 = 0$ and $$6 = d_3 + 2d_2$$ In particular $0 \le d_2 \le 3$.

• $d_2 = 0$ gives $d_3 = 6, d_4 = 3$
• $d_2 = 1$ gives $d_3 = 4, d_4 = 4$
• $d_2 = 2$ gives $d_3 = 2, d_4 = 5$, which contradicts the lemma,
• $d_2 = 2$ gives $d_3 = 0, d_4 = 6$, which contradicts the lemma.

QED

Let $d_n$ be the number of trees of degree $n$. By the lemma $n \le 4$. Then the number of instances (30) is the sum of the degrees for all trees, which is $$ 30 = 4d_4 + 3d_3 + 2d_2 + 1d_1$$ but $$9 = d_4 + d_3 + d_2 + d_1$$ Eliminating $d_4$ gives $$ 6 = d_3 + 2d_2 + 3d_1$$ So the total number of trees of degree $< 4$ is at most $6$, leaving at least $3$ 4-trees. By the lemma, the smallest degree possible is therefore $2$, so $d_1 = 0$ and $$6 = d_3 + 2d_2$$ In particular $0 \le d_2 \le 3$.

• $d_2 = 0$ gives $d_3 = 6, d_4 = 3$
• $d_2 = 1$ gives $d_3 = 4, d_4 = 4$
• $d_2 = 2$ gives $d_3 = 2, d_4 = 5$, which contradicts the lemma,
• $d_2 = 3$ gives $d_3 = 0, d_4 = 6$, which contradicts the lemma.

Let $n$ be the degree of a tree $T$. Then the $n$ sets containing $T$ consist of $2n$ instances other than those for $T$. If any two of these instances are for the same tree, then the two sets they are in have two points in common (the shared point and $T$), which is not allowed. Thus we must have $2n + 1$ distinct trees (including $T$). So $2n + 1 \le 9$, and $n \le 4$. If $n = 4$, then all trees are represented, so the 4-tree shares a set with every other tree. Now for any tree $T$, it must share a set with every 4-tree, so the count $d_4$ of 4-trees satisfies $d_n \le 2n$, or $n \ge \frac{d_n}2$

Let $n$ be the degree of a tree $T$. Then the $n$ sets containing $T$ consist of $2n$ instances other than those for $T$. If any two of these instances are for the same tree, they cannot be in the same set, and so the two sets they are in have two points in common (the shared point and $T$) which is not allowed. Thus we must have $2n + 1$ distinct trees (including $T$). So $2n + 1 \le 9$, and $n \le 4$. If $n = 4$, then all trees are represented, so the 4-tree shares a set with every other tree. Now for any tree $T$, it must share a set with every 4-tree, so the count $d_4$ of 4-trees satisfies $d_4 \le 2n$, or $n \ge \frac{d_4}2$

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. Also, every tree is in at least one row.

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}$$ 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.

Addendum

Combinatorically, the "441" case is possible (the above does not prove this, but it is easy enough to figure out an example), so to disprove it requires geometry. Because all 4 degree-4 trees share a row with the degree-2 tree, the two rows meeting at the degree-2 tree must consist ony of it and the degree-4 trees. The row can either form a "V", a "T", or an "X" shape, with the degree-2 tree being the point of intersection. Of the 4 degree-4 trees, there are ${4\choose 2} = 6$ ways of selecting 2 trees from them. Each such pair defines a row (since degree-4 trees form rows with all other trees). Of those 6 lines, there are only ways that 2 can be chosen so that they don't have a degree-4 tree in common. So there are only 3 intersections possible that are not degree-4 trees. One of these is the degree-2 tree, leaving only 2 intersections available for degree-3 trees to possibly fill.

Now suppose that a degree-3 tree is in one of those intersections. Then two of its rows contain all of the degree-4 tree, and as the degree-2 tree is already satisfied, the remaining row of the degree-3 tree must consist of only other degree-3 trees. For each of the 2 degree-3 trees in this row, one of their 3 rows does not contain any degree-4 trees. Therefore the other two rows must contain all 4 of the degree 4 trees, which means that both of these degree-3 trees must also be at the intersection of 2 of the 6 rows discussed above. But we have 3 trees, and only 2 intersections, so this is impossible. Thus, every row must contain at least one degree-4 tree.

Of the 6 rows defined by the degree-4 trees, two intersect in the degree-2 tree. Each of the others must have a degree-3 tree as their third tree, and by the previous paragraph, each degree-3 tree can only lie on one of these rows. So the 4 degree-3 trees must be placed one on each of these lines. Hence the configuration must look like one of the following: In each case, I've labeled the 4 rows determined by the degree-4 trees as $A, B, C, D$. The degree-4 trees themselves are labeled by the two rows on which they lie. For example, the tree at the intersection of $A$ and $B$ is labeled $AB$. I've further divided each line into regions based on the interesections, and in the case of line $A$, by other points (the open circles) that represent where certain parallels intersect it. So $A$ is divided up into segments and rays $A1, A2, A3, A4, A5, A6$. For now, assume that none of the rows is parallel.

In all cases, the 3-tree on row $A$ forms rows with 4-trees $BD$ and $CD$. These rows must contain a 3-tree as their 3rd tree, but the only ones available are the 3-tree on rows $C$ and $B$, respectively. Depending on the region of $A$ that the $A$ 3-tree (or just "$A$-tree") is in, the $B$ and $C$ trees have specific regions of their rows where they must lie. The $B$-tree forms a row with $AC$ whose 3rd tree must be the $D$-tree, whose region is dependent on the region of the $B$-tree. Similarly, the $C$-tree forms a row with $AB$ that also must include the $D$-tree, and also requires a specific region depending on the region of the $C$-tree. In all cases it is seen that for the same starting $A$-tree region, the resulting regions for the $B$ and $C$ trees require different regions for the $D$-tree. Thus it is always impossible for solution to exist with four 4-trees, four 3-trees and one 2-tree.

In the tables for each case below, the $A$ column gives a region for the $A$-tree. The $B$ and $C$ columns show the regions for the $B$ and $C$-trees required by the $A$-tree. The $BD$ column shows the regions for the $D$-tree required by the $B$-tree region, and the $CD$ column shows the regions for the $D$-tree required by the $C$-tree region. In all cases, these disagree.

$$\text{ V - Shape}$$ $$\begin{array}{c|cc|cc} A & B & C & BD & CD\\\hline A1 & B4 & C2 & D3 & D2\\A2 & B1 & C2 & D3 & D2\\A3& B2 & C3 & D1/D4 & D3\\A4 & B3 & C4 & D2 & D1/D4\\A5 & B3 & C1 & D2 & D1\\A6 & B4 & C2 & D3 & D2\end{array}$$

$$\text{ T - Shape}$$ $$\begin{array}{c|cc|cc} A & B & C & BD & CD\\\hline A1 & B4 & C1 & D2 & D1/D4\\ A2 & B1 & C1 & D2 & D1/D4\\ A3 & B1 & C4 & D2 & D4\\ A4 & B2 & C3 & D1/D4 & D3\\ A5 & B3 & C2 & D3 & D2\\ A6 & B4 & C1 & D2 & D1/D4\end{array}$$

$$\text{ X - Shape}$$ $$\begin{array}{c|cc|cc} A & B & C & BD & CD\\\hline A1 & B1 & C2 & D2 & D1/D4\\ A2 & B4 & C2 & D2 & D1/D4\\ A3 & B3 & C3 & D1/D4 & D3\\ A4 & B2 & C4 & D3 & D2\\ A5 & B2 & C1 & D3 & D2\\ A6 & B1 & C2 & D2 & D1/D4\end{array}$$

Finally, the cases where some of the rows are parallel can be considered as limiting cases of the non-parallel versions above, where some of the regions shrink to 0. But the regional relations do not change, so they parallel cases are still impossible.

Thus the only solutions must have three 4-trees, and six 3-trees.

I've completely rewritten this post to hopefully be more coherent.

The geometric puzzle suggests a related combinatorial puzzle:

Given nine objects, how many non-isomorphic collections are there of ten sets of three objects each, such that no two of the sets have more than one object in common?

Where two collections are isomorphic if there is a permutation of the 9 objects (trees) that transforms one collection into the other.

Every solution to the geometric puzzle provides a solution to the combinatorial one. Solutions to the combinatorial puzzle thus restrict the possibilities for solutions to the geometric one, and provide guidance on finding them.

The combinatorial puzzle admits only 4 solutions:

Theorem: The following are the only solutions to the combinatorial puzzle:

• Objects: $\{A, B, C, 1, 2, 3, 4, 5, 6\}$ Collections: $$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35$$ $$ABC, A14, A25, A36, B16, B24, B35, C13, C26, C45$$ $$AB1, AC2, BC3, A34, A56, B46, B25, C16, C45, 123$$
• Objects: $\{A, B, C, D, 1, 2, 3, 4, *\}$ Collections: $$AB*, CD*, AC1, AD2, BC3, BD4, A34, B12, C24, D13$$

Proof:

Given such a collection, define an instance is a set $S$ in the collection, and a tree $t$ with $t\in S$. As there are $10$ sets of $3$ trees each, there are $30$ instances in all. Define the degree of a tree to be the number of instances of which it is a part. A tree of degree $n$ is called an $n$-tree. Since there are $9$ trees, the average degree of a tree is $\frac {30}9 = 3\frac13$. Therefore, some trees must have degree $4$ or more.

Lemma:

• The maximum degree for any tree is $4$.
• Any 4-tree shares a common set with every other tree.
• The minimum degree for any tree is at least half the number of 4-trees.

Proof:

Let $n$ be the degree of a tree $T$. Then the $n$ sets containing $T$ consist of $2n$ instances other than those for $T$. If any two of these instances are for the same tree, then the two sets they are in have two points in common (the shared point and $T$), which is not allowed. Thus we must have $2n + 1$ distinct trees (including $T$). So $2n + 1 \le 9$, and $n \le 4$. If $n = 4$, then all trees are represented, so the 4-tree shares a set with every other tree. Now for any tree $T$, it must share a set with every 4-tree, so the count $d_4$ of 4-trees satisfies $d_n \le 2n$, or $n \ge \frac{d_n}2$

Let $d_n$ be the number of trees of degree $n$. By the lemma $n \le 4$. Then the number of instances (30) is the sum of the degrees for all trees, which is $$ 30 = 4d_4 + 3d_3 + 2d_2 + 1d_1$$ but $$9 = d_4 + d_3 + d_2 + d_1$$ Eliminating $d_4$ gives $$ 6 = d_3 + 2d_2 + 3d_1$$ So the total number of trees of degree $< 4$ is at most $6$, leaving at least $3$ 4-trees. By the lemma, the smallest degree possible is therefore $2$, so $d_1 = 0$ and $$6 = d_3 + 2d_2$$ In particular $0 \le d_2 \le 3$.

• $d_2 = 0$ gives $d_3 = 6, d_4 = 3$
• $d_2 = 1$ gives $d_3 = 4, d_4 = 4$
• $d_2 = 2$ gives $d_3 = 2, d_4 = 5$, which contradicts the lemma,
• $d_2 = 2$ gives $d_3 = 0, d_4 = 6$, which contradicts the lemma.

Consider the case $d_2 = 1, d_3 = 4, d_4 =4$. Label the 4-trees $A, B, C, D$, the 3-trees $1, 2, 3, 4$, and the 2-tree "$*$". Since the 2-tree shares sets with all $4$ 4-trees, those sets must be $AB* := \{A, B, *\}$ and $CD*$. There cannot be set of just 4-trees, as any such set would share two trees with $AB*$ or $CD*$. Therefore the sets shared by pairs of 4-trees must have a 3-tree as the third member. By relabeling we can take $AC1$ and $AD2$ as two of the sets. The 4th set for $A$ must be $A34$, as all other trees have been paired with $A$. Suppose $BC2$ were also a set. Then $C34$ would also have to be as $C$ has been paired with all other trees. This conflicts with $A34$, so it cannot be that $BC2$ is a set. Therefore, relabeling if needed, we can take $BC3$ as set, and for similar reasons $BD4$. The remaining sets must be $B12, C24, D13$, again as these are the only remaining trees the 4-trees have not been paired with. This completes the list given in the theorem for this case. 

For the case $d_3 =6, d_4 = 3$, label the 4-trees $A, B, C$, and the 3-trees $1,2,3,4,5,6$.

1. Suppose that the 4-trees do not share a common set. In this case we can label the trees so that $AB1, AC2, BC3$ are sets. Each of $A, B, C$ have two more sets each, which they share with $2$ 3-trees. By relabeling, three of these are $A34, A56, B46$. This also requires $B25$. $C$ remains to be paired with $1, 4, 5, 6$, but $46$ and $56$ have already occurred, so the two sets must be $C16$ and $C45$. Finally $123$ makes up the last set.
2. When $ABC$ is a set, the remaining $9$ sets must consist of 3 sets each for $A, B, C$ matching them with a pair of 3-trees. This gives us 9 choices of pairs of 3-trees, of which there are ${6\choose2} = 15$ total, chosen so that each tree appears in 3 of the pairs. To find out how many non-isomorphic choices there are, it is easier to examine the $6$ pairs that were not picked. Since each tree appears in 5 pairs overall, it must appear in exactly two pairs of the leftovers. This allows us to form paths. For example, starting at 1, choose one of the two trees paired with it (say 3), then take the other tree paired with 3 (say 6), then the other tree paired with 6, and so on. As there is always exactly one other paired tree, this cannot end until you come back to 1, forming a loop. Each tree lies in such a loop, each loop has length at least $3$, and the sum of all loop lengths is $6$. So there are only two choices: a loop of length $6$, or $2$ loops of length $3$. Any two loops of length $6$ are isomorphic to each other, as are any pairs of loops of length $3$. The remainders for $$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35$$ form $2$ loops of length $3$, while the remainders for $$ABC, A14, A25, A36, B16, B24, B35, C13, C26, C45$$ form a loop of length $6$. This exhausts all cases, so the theorem is proved.

QED

There is not a 1-1 correspondence between combinatorial solutions and geometric solutions. Indeed, the two geometric solutions found so far both correspond to $$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35$$.

In fact,

Theorem: There is no geometric solution that corresponds to $$AB*, CD*, AC1, AD2, BC3, BD4, A34, B12, C24, D13$$.

Proof: Suppose there is. Then the rows corresponding to $AB*$ and $CD*$ form either a V, T, or X shape, with the intersection at $*$. Assuming no lines are parallel, the 3-trees must lie somewhere on the lines shown. Rows formed by the 3-tree on a line and a 4-tree not on it must also pass through a 3-tree on another line. So the location of the first 3-tree determine the location of the second 3-tree. Placing the 3-tree from the $AD$ line in varying regions of that line determines regions for the 3-trees on the $AC$ and $BD$ lines, which in turn each require regions for the 3-tree on the $BC$ line. But in all cases, the required regions on the $BC$ line do not overlap, making it impossible to place this tree. The case when some of the lines are parallel can be considered in the limit, and thus fail as well. It is impossible to construct a geometric solution for this combitorial case.

$$\text{ V - Shape}$$ $$\begin{array}{c|cc|cc} AD & AC & DB & BC(AC) & BC(BD)\\\hline AD1 & AC2 & BD4 & BC2 & BC3\\ AD2 & AC2 & BD1 & BC2 & BC3\\ AD3 & AC3 & BD2 & BC3 & BC4\\ AD4 & AC4 & BD3 & BC1/4 & BC2\\ AD5 & AC1 & BD3 & BC1 & BC2\\ AD6 & AC2 & BD4 & BC2 & BC3\end{array}$$

$$\text{ T - Shape}$$ $$\begin{array}{c|cc|cc} AD & AC & DB & BC(AC) & BC(BD)\\\hline AD1 & AC4 & BD4 & BC1/4 & BC3\\ AD2 & AC4 & BD1 & BC1/4 & BC3\\ AD3 & AC1 & BD1 & BC1 & BC3\\ AD4 & AC2 & BD2 & BC2 & BC1/4\\ AD5 & AC3 & BD3 & BC3 & BC2\\ AD6 & AC4 & BD4 & BC1/4 & BC3\end{array}$$

$$\text{ X - Shape}$$ $$\begin{array}{c|cc|cc} AD & AC & DB & BC(AC) & BC(BD)\\\hline AD1 & AC2 & BD4 & BC1/4 & BC2\\ AD2 & AC2 & BD1 & BC1/4 & BC2\\ AD3 & AC3 & BD2 & BC3 & BC1/4\\ AD4 & AC4 & BD3 & BC2 & BC3\\ AD5 & AC1 & BD3 & BC2 & BC3\\ AD6 & AC2 & BD4 & BC1/4 & BC2\end{array}$$

QED