Home  Il gomitolo di Gordio   Home
(Problema di Marzo 2011)


Il problema:

Dati più pezzi di lana (derivanti da un gomitolo tagliato come un nodo gordiano), Piotr scegli a caso due capi e li annoda tra di loro.

Bisogna stabilire quanti anelli si formeranno quando avrà annodato tutti i capi disponibili.


Soluzione:

Il numero medio di anelli dipende dal numero n degli spezzoni di lana; la dipendenza è logaritmica (vedi figura ottenuta con foglio di calcolo) per cui ad un grande aumento del numero degli spezzoni corrisponde un modesto aumento del numero di anelli.

 

Spiegazione:

Chiamerò A(n) il numero medio di anelli per n spezzoni.

E' chiaramente A(1)=1

Per n spezzoni abbiamo che, scelto il primo capo, la probabilità di scegliere come secondo capo quello appartenente allo stesso spezzone è 1/(2n-1) mentre la probabilità che si scelga un capo diverso è (2n-2)/(2n-1).
Nel caso che si scelga il capo dello stesso spezzone (o catena di spezzoni allacciati) il numero di anelli sarà uno in più di quelli che si potevano avere con il rimanente degli spezzoni.
Perciò il numero medio di anelli sarà A(n) = 1/(2n-1)(1+A(n-1))+(2n-2)/(2n-1)·A(n-1) = A(n-1) + 1/(2n-1).

Si ha la formula ricorsiva:

A(1) = 1

A(n) = A(n-1) + 1/(2n-1)

 


La simulazione calcola la media degli anelli che si formano effettuando l'operazione di annodatura 100 volte.
Se si considerano molti spezzoni da annodare (100 o più) i tempi di calcolo sono elevati (il tempo limite è di 60 secondi).

Numero di spezzoni (valore consigliato 10-300)