# Maximum number of umbrellas that can be added in a one kilometer beach?

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?

• Can you present a way to place umbrellas with which we can keep going for ever while satisfying the interval condition? – Benedict Randall Shaw Dec 20 '18 at 16:41
• 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? – John Douma Dec 20 '18 at 16:58
• The families are trying to fit this pattern for as long as possible – AspiringMat Dec 20 '18 at 16:59
• So they can agree on where to put their umbrellas from the start to keep this going as long as possible – AspiringMat Dec 20 '18 at 17:00
• 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. – Inactive - avoiding CoC Dec 20 '18 at 17:59