Imaginez n lolcats portant des petits bonnets ridicules numérotés de 1 à n. A ces n lolcats on associe n cheeseburgers numérotés également.
On mélange les lolcats en les jetant dans un sac hermétique, en fermant le sac et en le jetant dans la rivière la plus proche après l'avoir adéquatement lesté, puis en éclatant d'un rire satanique. Au sac, on aura préalablement attaché un fil fixé à un arbre en bordure de rivière, et ce fil nous permettra, une semaine plus tard, de récupérer nos reste de lolcats dans un état de conservation passablement correct.
Les n petites tombes qu'on a creusé au fond du jardin contiennent chacune un des cheeseburgers numérotés. Hélas, les infiltrations d'eau dans le sac pourtant vendu comme hermétique ont abimé les petits bonnets en papier des lolcats au point de rendre illisible leurs numéros. En dépit du protocole, on décide alors de déposer les dépouilles humides dans les petites tombes creusées, mais de manière aléatoire.
Quelle chance y a-t-il qu'aucun lolcat n'ai été posthumement associé à son cheeseburger attitré ? Et pourquoi me forcez-vous à gâcher bêtement mes cheeseburgers plutôt que de vous les offrir en récompense ?
03 avril 2010
I CAN HAS COMBINATORICS?
11 commentaires:
Je dirais (n-1)!/n!, mais peut-être que je vais devoir enlever Bac S Spé Maths de mon CV.
Ou ton brevet des collèges :D
(n-1)!/n!=1/n par simplification
A part ça je suis d'accord avec le résultat de Laurent, surtout que pour n=2 ça a l'air d'être juste
Et bien non. N'oubliez pas que chaque choix influence les choix suivants. J'ai n-1 façons de placer le premier lolcat, mais ensuite, si le premier lolcat a été associé au cheeseburger du deuxième, j'ai encore n-1 façons de placer le deuxième.
Les premières valeurs sont :
1/2 pour n=2
1/3 pour n=3
9/24 pour n=4
En fait ça revient à compter le nombre de permutations de l'ensemble à n éléments qui n'ont pas de points fixes.
Pour n=4, les permutations sans point fixe sont soit des cycles de longueur n, soit des produits de deux transpositions à support disjoint (une double transposition).
Il y a 3 double transpositions possible, et 3*2*1=6 cycles de longueur 4, donc 9 en tout.
Pas mal max, mais j'attends le cas général pour te couvrir de gloire.
Au risque de dire de la merde encore une fois, je dirais que les X(n) possibilités où le lolcat n'est pas avec le cheeseburger sont pour n >= 4:
X(n) = (n-2)(1*X(n-2)+X(n-1)) + 1*(1*X(n-2)+X(n-1))
X(n) = (n-1)(X(n-1)+X(n-2))
Et X(2) = 1, et X(3) = 2.
En tous cas, ça marche pour 4...
Désolé de ne pas t'avoir répondu avant Laurent, mais ça m'a l'air bon, je validerai si tu m'expliques ton raisonnement.
Ouais, ne sois pas désolé, mais bon, je ne me rappelle plus.
Bon Laurent, tu avais la bonne réponse.
J'ai poussé le calcul plus loin il y a quelque temps afin de dé-récursiver la solution, et je peux donc dire qu'il y a une solution simple non-récursive au problème, même si les calculs ne sont pas totalement triviaux.
Je la posterai si j'ai la motivation.
J'attends ce moment avec impatience, je boirai une bière pour fêter cela. Et en attendant, j'ai bu une bière pour me récompenser en avance.
Enregistrer un commentaire