1 2 5 7 8
3 4 6 9 10
Quanti sono i modi possibili di sistemare i barili? Non è facile dimostrare che la risposta è
|
Un mercante di Bagdad ha in vendita dieci barili di un balsamo prezioso, sistemati e numerati, da 1 a 10, nel modo indicato nel disegno.
Più piccolo è il numero del barile, più grande è il suo valore. Nel disporre i barili il mercante usa
una regola precisa: non collocare mai un barile sotto o a destra di uno di minor valore.
La collocazione raffigurata è la più semplice possibile per soddisfare questa condizione, ma ce ne sono
altre possibili. Ad esempio: 1 2 5 7 8 3 4 6 9 10 Quanti sono i modi possibili di sistemare i barili? Non è facile dimostrare che la risposta è | |
Per N=1 la risposta è facile:
1
2
è l'unica soluzione. E infatti C(2,1)/2 = 2/2 = 1.
Per N=2 è pure facile:
1 2 1 3
3 4 2 4
2 soluzioni. E infatti C(4,2)/3 = 6/3 = 2.
È facile e veloce calcolare
C(2*n,n)/(n+1) if n=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}.
Per studiare il problema occorre invece mettere a punto un programma; proviamo a farlo in una situazione che sappiamo controllare, per poi
modificarlo e generalizzarlo per studiare altre situazioni:
M=0; z=1:4; for(a in z)
for(b in z) if(b!=a)
for(c in z) if(c!=b & c!=a)
for(d in z) if(d!=c & d!=b & d!=a)
if(a<b & c<d & a<c & b<d) {print(c(a,b,0,c,d)); M=M+1}
# 1 2 0 3 4 scrivo ogni soluzione su una riga, usando "0" come separatore
# 1 3 0 2 4
M
# 2 Verifica usando i coefficenti binomiali:
choose(2*2,2)/(2+1)
# 2
N=3
M=0; z=1:6; for(a in z)
for(b in z) if(b!=a)
for(c in z) if(c!=b & c!=a)
for(d in z) if(d!=c & d!=b & d!=a)
for(e in z) if(e!=d & e!=c & e!=b & e!=a)
for(f in z) if(f!=e & f!=d & f!=c & f!=b & f!=a)
if(a<b & b<c & d<e & e<f & a<d & b<e & c<f) {print(c(a,b,c,0,d,e,f)); M=M+1}; M
# 1 2 3 0 4 5 6
# 1 2 4 0 3 5 6
# 1 2 5 0 3 4 6
# 1 3 4 0 2 5 6
# 1 3 5 0 2 4 6
# 5
choose(3*2,3)/(3+1)
# 5
Verifichiamo la cosa anche per N=4 e N=5. N=4:
M=0; z=1:8; for(a in z)
for(b in z) if(b!=a)
for(c in z) if(c!=b & c!=a)
for(d in z) if(d!=c & d!=b & d!=a)
for(e in z) if(e!=d & e!=c & e!=b & e!=a)
for(f in z) if(f!=e & f!=d & f!=c & f!=b & f!=a)
for(g in z) if(g!=f & g!=e & g!=d & g!=c & g!=b & g!=a)
for(h in z) if(h!=g & h!=f & h!=e & h!=d & h!=c & h!=b & h!=a)
if(a<b & b<c & c<d & e<f & f<g & g<h & a<e & b<f & c<g & d<h)
{print(c(a,b,c,d,0,e,f,g,h)); M=M+1}; M
# 1 2 3 4 0 5 6 7 8
# 1 2 3 5 0 4 6 7 8
# 1 2 3 6 0 4 5 7 8
# 1 2 3 7 0 4 5 6 8
# 1 2 4 5 0 3 6 7 8
# 1 2 4 6 0 3 5 7 8
# 1 2 4 7 0 3 5 6 8
# 1 2 5 6 0 3 4 7 8
# 1 2 5 7 0 3 4 6 8
# 1 3 4 5 0 2 6 7 8
# 1 3 4 6 0 2 5 7 8
# 1 3 4 7 0 2 5 6 8
# 1 3 5 6 0 2 4 7 8
# 1 3 5 7 0 2 4 6 8
# 14
choose(4*2,4)/(4+1)
# 14
N=5 (ci vuole qualche minuto):
M=0; z=1:10; for(a in z)
for(b in z) if(b!=a)
for(c in z) if(c!=b & c!=a)
for(d in z) if(d!=c & d!=b & d!=a)
for(e in z) if(e!=d & e!=c & e!=b & e!=a)
for(f in z) if(f!=e & f!=d & f!=c & f!=b & f!=a)
for(g in z) if(g!=f & g!=e & g!=d & g!=c & g!=b & g!=a)
for(h in z) if(h!=g & h!=f & h!=e & h!=d & h!=c & h!=b & h!=a)
for(i in z) if(i!=h & i!=g & i!=f & i!=e & i!=d & i!=c & i!=b & i!=a)
for(l in z) if(l!=i & l!=h & l!=g & l!=f & l!=e & l!=d & l!=c & l!=b & l!=a)
if(a<b & b<c & c<d & d<e & f<g & g<h & h<i & i<l & a<f & b<g & c<h & d<i & e<l)
{print(c(a,b,c,d,e,0,f,g,h,i,l)); M=M+1}; M
# 1 2 3 4 5 0 6 7 8 9 10
# 1 2 3 4 6 0 5 7 8 9 10
# ...
# 1 3 5 7 8 0 2 4 6 9 10
# 1 3 5 7 9 0 2 4 6 8 10
# 42
choose(5*2,5)/(5+1)
# 42 Le sistemazioni possibili per il nostro mercante
Avendo varie ore a disposizione si può trovare anche con N=6:
M=0; z=1:12; for(a in z)
for(b in z) if(b!=a)
for(c in z) if(c!=b & c!=a)
for(d in z) if(d!=c & d!=b & d!=a)
for(e in z) if(e!=d & e!=c & e!=b & e!=a)
for(f in z) if(f!=e & f!=d & f!=c & f!=b & f!=a)
for(g in z) if(g!=f & g!=e & g!=d & g!=c & g!=b & g!=a)
for(h in z) if(h!=g & h!=f & h!=e & h!=d & h!=c & h!=b & h!=a)
for(i in z) if(i!=h & i!=g & i!=f & i!=e & i!=d & i!=c & i!=b & i!=a)
for(l in z) if(l!=i & l!=h & l!=g & l!=f & l!=e & l!=d & l!=c & l!=b & l!=a)
for(m in z) if(m!=l & m!=i & m!=h & m!=g & m!=f & m!=e & m!=d & m!=c & m!=b & m!=a)
for(n in z) if(n!=m & n!=l & n!=i & n!=h & n!=g & n!=f & n!=e & n!=d & n!=c & n!=b & n!=a)
if(a<b & b<c & c<d & d<e & e<f & g<h & h<i & i<l & l<m & m<n & a<g & b<h & c<i & d<l & e<m & f<n)
{print(c(a,b,c,d,e,f,0,g,h,i,l,m,n)); M=M+1}; M
# 1 2 3 4 5 6 0 7 8 9 10 11 12
# 1 2 3 4 5 7 0 6 8 9 10 11 12
# ...
# 1 3 5 7 9 10 0 2 4 6 9 10 12
# 1 3 5 7 9 11 0 2 4 6 8 10 12
# 132
choose(6*2,6)/(6+1)
# 132
Questo è uno dei moltissini giochi matematici ideati da Henry Ernest Dudeney (1857–1930).
Vedi https://en.wikipedia.org/wiki/Henry_Dudeney.