Puzzle reference request: planting trees in a semicircle orchard

153 Views Asked by At

I saw this puzzle once, but cannot find any reference on this now. Can you find a reference?

In a semicircle orchard, trees are planted in the orchard in the given manner: after the $n^\text{th}$ tree is planted, the orchard is divided into $n$ equal sectors, and each sector must contain exactly one tree. The trees cannot be on the sector boundaries. How many trees can be planted in this manner?

The puzzle says that there's a proof that at most 17 trees can be planted. Also, a related question: if instead of a semicircle, the orchard is a circle, can more trees be planted?

Edit: The first problem is usually called "Irregularity of Distribution". A website that illustrates this is http://weitz.de/irr/

I have solved the second question. There's a pattern by which the trees can be planted and the sectors be divided, so that the trees can be planted endlessly.

Let the circle be $\mathbb{R}/\mathbb{Z}$, written as $[0, 1)$. Then the trees are planted in this manner:

$$t_1 = 0, t_2 = 1/2, t_3 = 1/4, t_4=3/4, ...$$

and in general, $\forall n \geq 1, 1 \leq i \leq 2^n$

$$t_{2^n + i} = t_i + 1/2^{n+1}$$

This has a very geometric meaning if you draw it out on a circle. Basically, for the points $2^n+1, ... 2^n+ 2^n$, just take the points $1, ... 2^n$ and shift them clockwise by $1/2^{n+1}$.

Then, after planting the $n$th tree, let the $n$ sectors be divided at the points $t_{n+1}, t_{n+1} + 1/n, ...$ Then each tree is in a unique sector.

1

There are 1 best solutions below

3
On BEST ANSWER

The puzzle may have originated with Steinhaus in his book, One Hundred Problems in Elementary Mathematics, pp. 6-7 and 61-64 of the 1964 edition. In a footnote, he attributes the solution to M Warmus.

A proof of the solution to a generalization appears in Berlekamp and Graham, Irregularities in the distribution of finite sequences, J Number Theory 2 (1970) 152-161.

The problem also appears as Example 63 in Guy, The second strong law of small numbers, Math Mag 63 (1990) 3-20.