4
$\begingroup$

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

  • 1
    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 http://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.2011-07-07
  • 0
    Thanks for the link. At least this is a hint that my program worked correctly. I still wonder how this "17" pops up.2011-07-07
  • 6
    This was discussed at http://math.stackexchange.com/questions/43311/choosing-points-in-fractions-of-the-unit-interval and good references are given there. One shows that 17 is maximal.2011-07-07
  • 0
    Thanks a lot, this is what I've been searching for.. just didn't have any name.2011-07-07
  • 0
    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.2011-07-07
  • 0
    The problem seems to mention _lots_ of numbers to me: I see $2, ... k, ...$2011-07-07
  • 0
    @Gerry: I think that (puzzle) is an appropriate tag. Partly because of the history of this problem. Partly because the techniques of solution use discrete techniques: computer search within a tree of subinterval determined by Farey fractions.2011-07-07
  • 0
    @Jyrki, thanks. I see your point, though I think "puzzle" belittles the problem, which is closely connected to some deep problems in the metric theory of distribution of sequences.2011-07-07
  • 0
    @Gerry: Oops. I didn't know that. I was having second thoughts myself, because a puzzle typically has a solution, more often than not with a lightbulb moment, and that doesn't seem to be the case here.2011-07-08

1 Answers 1

5

For old problems the "Bundeswettbewerb Informatik" offers detailed solutions. In your case you find the solution set here on page 16 to 38 (!). Also an optimal algorithm is presented which leads to the conclusion that 17 is the maximum.

  • 0
    Thanks for this link, too. Although I'd rather wanted to see a mathematical proof. I would still appreciate a short/nice argument that there is an upper bound.2011-07-07
  • 0
    The designed algorithm is a mathematical proof, if you want to make it waterproof you should formally proove its correctness. I don't think there is a good way to do this analytically.2011-07-07
  • 0
    I don't read German. Is this basically just a brute-force search or is there something more going on?2011-07-07
  • 0
    Basically yes (every combination is covered) but its done in a way that the search space is not too big. They use a bottom-up approach where they go backwards from the point where all tents are set.2011-07-07