Il mostro dei biscotti

[axpgn]

Hai $15$ vasetti contenenti $1,2,3,...,15$ biscotti, rispettivamente.
Il mostro dei biscotti può scegliere un qualsiasi sottoinsieme di vasetti e togliere lo stesso numero di biscotti da ognuno di questi vasetti.

Il mostro dei biscotti ce la fa a svuotarli tutti in meno di cinque mosse?


Cordialmente, Alex

[Drazen77]

Quattro mosse?

[gabriella127]

Spero di riuscire a spiegare a parole. $4$ step:

Step 1) Prende i vasetti 8-15 e ci toglie 8 da ognuno. Resta con un vasetto vuoto e due file di vasetti da 1 a 7.
Step 2) Prende i vasetti da 4 a 7, e ci toglie 4 da ognuno, e resta con due insiemi di vasetti da 0123 rispettivamente.
Togliamo gli $0$, restano in totale quattro file di vasetti da 123 biscotti rispettivamente. Cioè:

(1 2 3) (1 2 3)
(1 2 3 ) (1 2 3)

Step 3) Prendiamo in un'unica mappazza tutti i vasetti con $2$ e $3$, e da ognuno togliamo $2$. Restano solo vasetti con $0$ o $1$.

Step 4) Prendiamo tutti i vasetti con $1$ e togliamoci l'unico biscotto.

Fine.

[axpgn]

Bravi!

Questo problema è conosciuto come "The Cookie Monster Problem" e c'è un po' di letteratura a riguardo

Per quanto ne so, non c'è un algoritmo che funzioni in generale però sono stati stabiliti gli "upper and lower bounds" ovvero dato un insieme di $n$ vasetti, contenenti ciascuno un diverso numero di biscotti non nullo, si ha che il numero $m$ di mosse necessario è $\floor(log_2 n)+1<=m<=n$

Cordialmente, Alex