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