Suppose we have a beach of length $1-$km. Suppose one Day $0$, the beach is empty.

One day $1$, a family comes and puts their umbrella at some point in the beach. This point is fixed forever and cannot be moved.

On day $2$, a new family comes and puts their umbrella in a new coordinate. This umbrella is now fixed forever. However, we are guaranteed that the intervals $[0,\frac{1}{2}], [\frac{1}{2},1]$ each have $1$ umbrella; the old and the new one.

In general, on day $i$, a new family comes in and fixes a new umbrella. We're guranteed that the interval $[0,\frac{1}{i}], ..., [1-\frac{1}{i}, 1]$ all have one umbrella each.

The question is, what is the maximum day $t$ such that we cannot add a new umbrella where the $t$ sub intervals would have $1$ umbrella each?

The question answer say $18$, but I don't see how this is true?! Shouldn't we be able to keep going forever?

  • 1
    $\begingroup$ Can you present a way to place umbrellas with which we can keep going for ever while satisfying the interval condition? $\endgroup$ – Benedict Randall Shaw Dec 20 '18 at 16:41
  • $\begingroup$ Are the families trying to fit this pattern or is the problem claiming it always works? For example, suppose after day $2$ there is an umbrella just slightly to the left of $\frac{1}{2}$ and another just slightly to the right of $\frac{1}{2}$ so that both are contained in $(\frac{1}{3},\frac{2}{3})$. How can we place a third umbrella so that the condition is met? $\endgroup$ – John Douma Dec 20 '18 at 16:58
  • $\begingroup$ The families are trying to fit this pattern for as long as possible $\endgroup$ – AspiringMat Dec 20 '18 at 16:59
  • $\begingroup$ So they can agree on where to put their umbrellas from the start to keep this going as long as possible $\endgroup$ – AspiringMat Dec 20 '18 at 17:00
  • 1
    $\begingroup$ I have seen this problem before, and the proof is by distinguishing many many cases and brute force/exhaustion. There is nothing deep, just track which are the possible intervals for the 1st, 2nd, 3rd, etc. umbrellas after the 1st, 2nd, 3rd, etc. round. $\endgroup$ – Inactive - avoiding CoC Dec 20 '18 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.