Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Empilement hasardeux Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=scarta]J'aime :D 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 :D 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 : 2E(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[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Riri, Fifi et ?* Retour Résumé de la discussion Sydre 07-03-2022 14:52:35 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? 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