# The “beach problem”: does anyone know it? or know how to solve it?

The following problem was given some years ago in the German computer-science contest for pupils ("Bundeswettbewerb Informatik"). It was originally wrapped in a story which I will briefly translate below. My second "translation" already includes my understanding of the problem in terms of pure mathematics.

The fascinating thing for me is the following: Although the problem doesn't mention any numbers, my computer program only found a solution for 17 tents (but none for 18 and higher). I wonder if there is a rigorous proof for this.

Consider a beach of a finite length. During one summer period there are several campers coming to this beach (one after each other). The first camper may put his tent anywhere he likes. When the second camper arrives the beach will be divided into two equal parts and the second one must put his tent into the free half. Generally, if the k'th camper arrives, the beach is divided into k equal parts and there must be only one tent per part.

The question is the following: Given that all campers choose there positions perfectly, how many campers may arrive until there is no way to add another one (besides moving tents)?

My mathematical translation assumes the following:

• Tents are point-like
• The beach has a size of 1 (consider the real numbers from 0 to 1)
• If a camper puts his tent on the position 0.5 he is by definition in the right half ([0.5, 1])
• Therefore we can also think of the beach as the open interval $[0, 1)$

For a given natural number N, is there a way to choose a sequence of (ordered) points $P_1, P_2, \dots, P_N$ on the interval $[0, 1)$ such that for each $k \in \{1,\dots,N\}$ and each $l \in \{1, \dots,k\}$ there exists only one $i \in \{1, \dots, k\}$ such that

$\frac{l-1}{k} \le P_i < \frac{l}{k}$

I would like to know the following:

• Is there a solution for any N or is there a maximum N?
• If there is a maximum N, which one is it?

Investigating this problem I was only able to simplify it a bit. For example: it is enough to consider the "boundaries" as possible points for the tents. Assume you want to find a solution for $N=4$ (which is quite easy :-)). It is enough to consider the following possible positions:

$0, 1/4, 1/3, 1/2, 2/3, 3/4$

Thinking about this also brought up Eulers $\varphi$ function, because the number of such possible positions is $\sum_{k=1}^N \varphi(k)$. So the problem could be related to prime numbers.

Any hints pointing to a solution are appreciated. I also would like to know if you are aware of similar problems or maybe other formulations of the same problem?

Link to the original problem, German (see page 6): http://www.bundeswettbewerb-informatik.de/uploads/media/bwi23/runde2/aufgaben232.pdf

-
This shows up every now and then. I've seen it expressed in terms of using flagpoles as opposed to tents. I may have seen it on this forum or another. The first google hit I got is mathforum.org/kb/message.jspa?messageID=391377&tstart=0 A brute force computer check shows that 17 is the maximum. I don't recall having seen an elegant solution. – Jyrki Lahtonen Jul 7 '11 at 12:20
Thanks for the link. At least this is a hint that my program worked correctly. I still wonder how this "17" pops up. – shark.dp Jul 7 '11 at 12:31
This was discussed at math.stackexchange.com/questions/43311/… and good references are given there. One shows that 17 is maximal. – Ross Millikan Jul 7 '11 at 12:38
Thanks a lot, this is what I've been searching for.. just didn't have any name. – shark.dp Jul 7 '11 at 12:40
This has little to do with prime numbers or infinite series, so I replaced those tags with "uniform distribution". There's probably something better that I'm not thinking of. – Gerry Myerson Jul 7 '11 at 12:45