Soluzione all'enigma 26, proposto da Stefano P. il 26 gennaio 2005
Il piccolo Gigetto è un bambino molto creativo, uno che, per
la gioia del portafoglio dei suoi genitori, riesce a divertirsi con poco e passa ore a
giocare con i piccoli oggetti della vita quotidiana che trova in casa. Oggi, in
particolare, ha trovato in un armadietto della cucina, i 13 contenitori della Tupperware®
della mamma (per chi non sapesse che cosa sono: semplicemente dei contenitori in plastica
di diverse dimensioni che si possono inscatolare uno dentro l'altro) e subito si è
ingegnato per trovare un modo divertente di giocarci. La sua idea è stata questa: dopo
aver osservato che tutti e 13 i contenitori hanno dimensioni diverse, ne sceglie uno
qualsiasi che non sia, però, il più grande. Quindi inserisce il contenitore scelto
dentro uno qualsiasi degli altri (ovviamente lo deve inserire dentro uno di quelli più
grandi, altrimenti non può farcelo entrare!), e procede così, inserendo i due
contenitori già inscatolati dentro un terzo più grande, e così via fino ad
inserire la sua matrioska dentro il contenitore più grande di tutti; a questo punto il
gioco è finito. Ovviamente al termine del gioco non tutti i contenitori sono stati
utilizzati ed inscatolati uno dentro l'altro: alcuni possono essere stati saltati nella
procedura, ma questo non è un problema. Ben presto, nonostante la fantasia e la
creatività che lo contraddistinguono, il piccolo Gigetto comincia ad annoiarsi a giocare
in questo modo, e, visto che oltre alle succitate qualità il frugoletto dispone di una
curiosità ed una sagacia notevoli, decide di provare a scoprire in quanti modi diversi è
possibile giocare il suo gioco, ovvero in quanti modi diversi si possono inscatolare i 13
tupperware della mamma mai partendo dal più grande ma terminando sempre con il più
grande. Questa nuova sfida lo impegna per un'oretta circa, ma alla fine, visto che oltre
alle succitate qualità il piccolo dispone anche di una notevole intelligenza, produce la
sua risposta e corre orgoglioso a raccontare alla mamma come ha fatto...
Voi volete essere da meno? :-)
Ecco la soluzione proposta da Paolo P.
Immaginiamo per semplicità che i contenitori siano 4 e poi generalizzeremo. Le soluzioni
possibili sono
1 2 3 | 4
---------
0 0 X | X
0 X 0 | X
0 X X | X
X 0 0 | X
X 0 X | X
X X 0 | X
X X X | X
dove i numeri da 1 a 4 rappresentano il conenitori dal più piccolo al più grande e dove:
- X significa che prendo quel contenitore
- 0 significa che non lo prendo.
Sono tutti i numeri in binario di tre cifre partendo da 1, quindi la soluzione è
2^(N-1) - 1
dove N è il numero di contenitori.
Nel caso considerato N = 13 quindi il numero di possibilità è
(2^12) - 1 = 4095