Picking marbles

Question

We have 15 urns each of them having a different number of marbles, from 1 to 15. We start by picking the same number of marbles from each of the urns we choose. We repeat the process until we have picked all marbles. What is the minimum number of days we can finish picking all marbles? Just to clarify that it is not necessary to pick marbles from EVERY urn.

I don't think I can make it in less than 5 moves (start by picking 6, then 4, then 3, then 2 and 1) but I am fairly sure it can be done in 4 or maybe less.

Any ideas?

Answer 1

You can look at your urns as an array of 4 bit integers:
$0001_b$
$0010_b$
$0011_b$
...
$1111_b$

On every step you can set one bit to $0$ on every integer for which it isn't already 0. There are 4 bits so you can do it in 4 steps. If we go back to decimal, you're removing 8, then 4, then 2, then 1.

In fact we can also prove that $n$ is the minimum number of steps for $n$-digit urns through a recursion on the number of digits.

Answer 2

It is possible in 4 days:

First day you reduce the number of balls by 8 in urns with at least 8 balls. So now each urn has at most 7 balls.

Second day you reduce the number of balls by 4 in urns with at least 4 balls. So now each urn has at most 3 balls.

Third day you reduce the number of balls by 2 in urns with at least 2 balls. So now each urn has at most 1 ball.

Last day you took balls from all the nonemty urns.