Recoger canicas

Question

Tenemos 15 urnas, cada una de ellas con un número diferente de canicas, del 1 al 15. Empezamos cogiendo el mismo número de canicas de cada una de las urnas que elegimos. Repetimos el proceso hasta que hayamos cogido todas las canicas. ¿Cuál es el número mínimo de días en que podemos terminar de recoger todas las canicas? Sólo aclarar que no es necesario coger canicas de TODAS las urnas.

No creo que pueda hacerlo en menos de 5 movimientos (empezar eligiendo 6, luego 4, luego 3, luego 2 y 1) pero estoy bastante seguro de que se puede hacer en 4 o quizás menos.

¿Alguna idea?

Answer 1

Puedes ver tus urnas como una matriz de enteros de 4 bits:
$0001_b$
$0010_b$
$0011_b$
...
$1111_b$

En cada paso puedes poner un bit a $0$ en cada entero para el que no es ya 0. Hay 4 bits por lo que se puede hacer en 4 pasos. Si volvemos al decimal, estás quitando 8, luego 4, luego 2, luego 1.

De hecho, también podemos demostrar que $n$ es el número mínimo de pasos para $n$ -digit recurre al número de dígitos.

Answer 2

Es posible en 4 días:

El primer día se reduce el número de bolas en 8 en las urnas con al menos 8 bolas. Así que ahora cada urna tiene como máximo 7 bolas.

El segundo día se reduce el número de bolas en 4 en las urnas con al menos 4 bolas. Así que ahora cada urna tiene como máximo 3 bolas.

El tercer día se reduce el número de bolas en 2 en las urnas con al menos 2 bolas. Así que ahora cada urna tiene como máximo 1 bola.

El último día sacaste pelotas de todas las urnas no emty.