Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 07-03-2022 14:52:35

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 236

empilrment hasardeux

Soit [latex]2[/latex] piles contenant au départ [latex]1[/latex] élément chacune.

On agit sur ce système comme suit:

1) On choisit une pile au hasard (de façon équiprobable) et on retire un élément de celle-ci pour l'empiler sur l'autre
2) Si une pile est vide on lui ajoute un nouvel élément

En combien de coups en moyenne parvient on à empiler [latex]n[/latex] éléments?
En combien de coups en moyenne parvient on à empiler [latex]n[/latex] éléments dans la 1ère pile?

  • |
  • Répondre

#0 Pub

 #2 - 08-03-2022 09:38:35

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1862

Empilement hasarduex

J'aime big_smile

Bon alors la première partie, à la rache :
- La condition pour avoir un empilement à n éléments est d'avoir au moins n éléments
- La seule façon d'ajouter un élément est d'avoir une configuration avec une pile vide
--> conclusion : la première fois qu'on arrive à n éléments, c'est lorsqu'on a 0-n ou n-0 (moins d'éléments : pas assez, plus d'éléments : on a forcément du passer par un empilement de plus de n blocs)

On part avec 2 blocs : combien de coups pour arriver à 3 ? puis à 4 ? puis à 5 ? etc...

- pour passer à 3 un coup suffit. Alors c'est logique, mais on va l'écrire de manière inutilement compliquée quand même, pour mieux comprendre la suite :
E = 1/2 x 1 + 1/2 x 1 = 1
(1 coup avec une chance sur 2 si c'est le bloc de droite qu'on bouge, et 1 coup avec une chance sur 2 si c'est l'autre, et dans les deux cas ça s'arrête ici)

- pour passer à 4 : on démarre sur 1-2
E = 1/2 x 1 + 1/2 x (E+1)
(soit on a fini - une chance sur 2 - soit on passe sur 2-1, qui est symétrique à 1-2 et qui a donc la même espérance, plus le coup qu'on vient de jouer)
Total: E = 2

- pour passer à 5 : on démarre sur 1-3
on va commencer à noter E1 le résultat en partant de 1-3, E2 pour 2-2
E1 = 1/2 x 1 + 1/2 x (1+E2) = 1 + 1/2 E2
E2 = 1/2 x (E1+1) + 1/2 x (E1+1) = E1 + 1
(traduction : la première équation pour terminer ou passer à 2-2, la seconde pour revenir à 1-3 ou passer à 3-1 qui est identique)
On arrive à E1 = 3

- pour passer à 6 depuis 1-4
2E1 = 2 + E2
2E2 = 2 + E1 + E2
E1 = 4

- pour passer à 7 depuis 1-5
2E1 = 2 + E2
2E2 = 2 + E1 + E3
2E3 = 2 + 2E2
E1 = 5

etc.. je pense qu'on a compris le principe big_smile
En gros, pour avoir n éléments répartis en 1-n depuis la configuration 1-(n-1), ou les configurations symétriques, il faut n-1 coups.

Démonstration un peu plus formelle, pour le cas de départ 1-n : on va construire un système d'équations
2E1 = 2 + E2
2E2 = 2 + E1 + E3
2E3 = 2 + E2 + E4
...
2E(n-1) = 2 + E(n-2) + E(n)
2E(n) = 2 + E(n-1)

Résolution du système:
E(n-1) = 2(E(n) - 1)
E(n-2) = 3(E(n) - 2)
E(n-3) = 4(E(n) - 3)
E(n-4) = 5(E(n) - 4)
E(n-5) = 6(E(n) - 5)
etc...
une petite récurrence montre que E(n-k) vaut (k+1)*(E(n) - k) pour les k < n-1
(supposons que c'est vrai, alors l'équation suivante donne :
2*E(n-k) = 2 + E(n-k+1) - E(n-k-1)
2*(k+1)*(E(n) - k) = 2 + k*(E(n) - k+1) + E(n-k-1)
E(n-k-1) = (k+2)*E(n) - 2k^2 -2k -2 + k^2 -k
E(n-k-1) = (k+2)*E(n) - k^2 -3k -2 = (k+2)*(E(n) - k+1) cqfd

et de fil en aiguille, on en arrive à E2 = (n-1)*(E(n) - n-2)
E1 = 2 + (n-1)*(E(n) - n-2)
Symétrie oblige, E1 = E(n) ==> 2E1 = 2 + (n-1)*(E1 - n-2)
(n-3) E1 = (n-1)(n-2)-2 = n^2 - 3n = n(n-3)
E1 = n

CQFD

Donc, pour passer de 1-1 à 1-2 il faudra 1 coup en moyenne, de 1-2 à 1-3 2 coups en moyenne, etc... et de 1-(n-1) à 1-n en n-1 coups

pour arriver à 1-n, il faudra 1+2+3+4+...+(n-1) = n(n-1)/2 coups en moyenne

La question 2 : j'y réfléchis

 #3 - 08-03-2022 14:29:16

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 236

Empilement hasardex

Très bon début scarta big_smile

 #4 - 08-03-2022 16:34:46

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1862

empilzment hasardeux

Petit résultat annexe (je ne sais pas encore s'il me servira pour la 2) : la probabilité d'inverser les piles entre les étapes 1-N et (N+1)-1 est de 1/(N+1)
et la probabilité de passer à l'étape suivante en restant avec la même pile est bien sur de N/(N+1)

Ca se démontre pareil que l'autre post, via des systèmes d'équations qui ont toutes la même tête

 #5 - 10-03-2022 15:17:06

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 236

Empilement hasardeuux

Merci à scarta, unique participant lol

La réponse à la 2ème question est le double de la réponse à la 1ère, c'est à dire [latex]n(n-1)[/latex]. Je laisse la démonstration aux curieux wink

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete