Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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 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
6  
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

1 Answer 1

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.

share|improve this answer
    
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. –  shark.dp Jul 7 '11 at 14:57
    
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. –  Listing Jul 7 '11 at 15:05
    
I don't read German. Is this basically just a brute-force search or is there something more going on? –  Michael Lugo Jul 7 '11 at 16:03
    
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. –  Listing Jul 7 '11 at 17:22

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.