J'aime

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
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

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