Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

"Tree-planting" puzzles are also known as "points and lines" puzzles. The English puzzle author and mathematician Henry Ernest Dudeney was very fond of them. In 1917, Dudeney published a collection of puzzles called "Amusements in Mathematics", which also contains the following classic puzzle:

Sir Isaac Newton's tree-planting puzzle: A farmer wants to plant 9 trees in such a way that there are 10 rows of 3 trees. How does he do this?

Note: the different rows are not allowed to be collinear.

P.S. I know of two different solutions. If you know any more that would be great and if you are able to prove that there aren't any more solutions that would be even greater. I consider two solutions different when there is no graph isomorphism possible between them.

share|improve this question
    
I assume that there must be a restriction that there can be no more than 10 rows of 3. If I have four trees in a row does that count as two rows of 3 (trees 1 to 3 and trees 2 to 4) or is there also a rule that rows can only intersect at a single point? If so, then could five trees in a line count as two rows of 3? – Hugh Meyers Mar 29 at 13:55
1  
@HughMeyers the different rows are not allowed to be collinear with each other – Ivo Beckers Mar 29 at 14:02
18  
Funny.. the way English is used by my peers in my region of the USA, "10 rows of 3 trees" means 30 trees, no more, no less. Looking at the highest voted answer and assuming it is at least on the right track, I would have said, "A famer wants to plant 9 trees so that 10 straight lines can be drawn that each pass through exactly 3 trees." – Todd Wilcox Mar 29 at 15:20
2  
Are you allowed to warp spacetime? – Mark Mar 29 at 21:25
1  
For those who want to read more about this, there are several external references to the so-called "Orchard-Planting Problem" on Wikipedia and MathWorld. The general problem is still apparently an area of active research, and apparently has some interesting ties to elliptic curves. – Michael Seifert Mar 30 at 13:29
up vote 4 down vote accepted

A third solution. I've been searching systematically for them (I've eliminated all the combinatorial solutions other than ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35 - it is the only one with geometric solutions).

To see that it is distinct from the others, note that it has a tree with 7 immediate neighbors.

9 rows solution

I believe that is all of them, though. Once I double check to make sure I haven't missed something, I try to put something together to show it.

share|improve this answer
    
Nice find! very impressive. Also interesting that unlike the other two solutions there is no line symmetry – Ivo Beckers Apr 2 at 19:13
    
@IvoBeckers - I would not be surprised if it could be redrawn with symmetry. This form is just what came up by my method of investigation. – Paul Sinclair Apr 2 at 21:13

I think there might be quite a lot of possible answers, but here is one of them:

Sorry for the bad MS Paint skills ;)
enter image description here
The numbers at the intersections represents the trees, and the lines are added to indicate the 10 "rows" of 3.


EDIT:

I think there might be quite a lot of possible answers, but here is one of them

Let's rephrase that to: "I think there are barely any possible answers, but here is the easiest one."

I tried to come up with another one, but the only one I was able to find eventually was already represented by Marius.

share|improve this answer

Legend:
1..9 are the trees.
X = empty space.

Solution 1:

1X2
X3X
456
X7X
8X9

Lines:

01. 148
02. 269
03. 136
04. 234
05. 678
06. 479
07. 456
08. 357
09. 159
10. 258

picture:

Solution 2 (built with my awesome ms paint skills):

Imgur

Lines:

01. 123
02. 165
03. 184
04. 295
05. 278
06. 376
07. 389
08. 345
09. 694
10. 587

share|improve this answer
    
you forgot 456 on your picture – Lord of dark Mar 29 at 16:31
1  
I didn't add the picture. Some good samaritan addet it. – Marius Mar 29 at 16:41
1  
Nice, those are the 2 I knew. I'll accept this answer in 24 hours if no one can come with more solutions or a proof that more solutions aren't possible – Ivo Beckers Mar 29 at 21:37
    
I'm not entirely sure, but I believe your two solutions are the only ones possible. I've tried to come up with a second solution, different from your second one, but every time I either end up with 8 lines of 3, or I need 10 coins in order to create the 9 lines. Pretty frustrating, especially since the solution I posted as answer (the same as your first one) was so easy to find.. – Kevin Cruijssen Mar 30 at 11:40
    
@KevinCruijssen. I've been trying to find a 3rd way but failed so far. But absence of evidence is not evidence of absence. We either find a mathematical proof that these are the only 2 options or we find a third one. We cannot conclude these are the only 2 because we're not smart enough to find a 3rd one :). – Marius Mar 30 at 11:50

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$

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.

441 disproof

$$\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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.