Jean n'a pas faim

[l'homme 5]

Bonjour à tous! Voici une question existentielle à laquelle il est bon de trouver une réponse pour comprendre le sens de la vie.

 

Chaque jour, la mère de Jean lui sert une bonne assiette remplie de 1000 spaghettis. Malheureusement, celui-ci n'a jamais faim. Faut dire, il est fin comme une crevette et ne fait jamais de sport. Mais ce n'est pas le sujet. Pour passer le temps (il n'a pas le droit de sortir de table puisqu'il ne mange pas ses spaghettis), il décide à chaque fois de nouer ses spaghettis comme suit:

- il choisit au hasard deux extremités  libres de spaghetti dans son assiette (pas forcément du même spaghetti) et les noue l'une à l'autre

-il recommence

-il recommence

...

 

Au bout de mille noeuds, il obtient un imbroglio de cycles de spaghettis dans son assiette, mais n'a plus d'extrémité libre de spaghettis à nouer.

La question est: combien de cycles de spaghettis construit-il en moyenne?

[timout 2 619]

j'ai essayé de 1 à 6 spaghettis, niveau probas j'ai quand meme une majorité de cercles de 1, mais je n'arrive pas à trouver de regles de calcul en fonction du nombre

[l'homme 5]

Si on se débrouille de la bonne manière, les calculs ne sont pas trop compliqués

[ribi 764]

À cette heure-ci j'ai toutes les raisons du monde de faire des erreurs.

Appelons C(n) le nombre de cycles construits en moyenne avec n spaghettis.

Révélation

On a C(n) = (C(n-1)+1)/(2n-1)+(2n-2)/(2n-1)*C(n-1)

puisqu'on a une chance sur 2n-1 de choisir l'extrémité du même spaghetti,.et 2n-2 chances sur 2n-1 de choisir l'extrémité d'un autre spaghetti, ce qui fait un "spaghetti" en moins après liaison.

Cela peut s'écrire : C(n) = C(n-1)+1/(2n-1)

Comme C(1) =1, on déduit que

C(n) est la somme des 1/(2i-1), i variant de 1 à n.

Pour n= 1000, cela ferait 4,435633 cycles environ en moyenne.

Mon logiciel de calcul formel donne : 1/2 ψ (2001/2)+1/2 + ln(2) avec ψ la fonction digamma et la constante d'Euler.

On est très proche de ln(4000)/2+1/2

 

[l'homme 5]

Bien joué pour la récurrence

J'avais pensé à un autre raisonnement:

Révélation

Lorsqu'on noue le Ne noeud, on choisit un fil et il reste (2000-2N-1) extrémités libres dans l'assiette. Dont une seule  permet de boucler un cycle.

On retrouve la somme des 1/2i-1