2^20 est le nombre de files differente qu´il peut y avoir si on ne considere pas le pb du rendue de monnaie. Donc la bonne reponse est ( normalement) inferieur à ce nombre

Eh t´as oublié de réfléchir

2^20, c bcp trop, déjà ça inclue la liste avec que des gens à 5 ou 10 euros, or ils sont pas plus de 10.

C´est vraiment prise de tête ce truc. Enfin bref j´ai pas trop envie d´y réfléchir pour le moment, on verra d´ici une ou deux semaines. Bonne chance à vous

_XboxMan_ : 20!*(1-(10!)^2/(14!6!))/(10!)^2 est sûrement un entier car ça vaut C(10,20)-C(6,20) où C(k,n) est le nombre de combinaison de k éléments parmi n sans ordre. Tu as du faire une erreur de calcul.

Je n´avais pas vu que personne ne connaissait la solution, désolé.

Pour expliquer mon raisonnement ( ça ne va pas être facile sans dessin ! ) :
Si on considère que les personnes de la file sont toutes différentes 2 à 2 ( même si elles ont le même billet), il y a en fait 20! ( 20 choix pour le premier, 19 pour le 2e,... 1 pour le 20e). Il suffit donc de dénombrer le nombre de mauvais choix. Mais comme on ne sait a priori pas faire, on va essayer de le mettre en bijection avec un ensemble qu´on sait dénombrer.
On va représenter les différentes files possible spar des suites finies telle que :
u0=0
u(n+1)=u(n)+1 si le ( n+1)ieme element de la file à un billet de 5 euros
u(n+1)=u(n)-1 si le ( n+1)ieme element de la file à un billet de 10 euros
Nécessairement, comme on a dix personnes de chaque type, on a u20=0.
En représentant les suites dans le plan, on obtient une famille de chemins reliant ( 0,0) à ( 20,0).
Regardons maintenant comment se caractérisent les mauvaises files : ce sont celles dont le chemin associé atteint la droite D:y=-1. Soit c un tel chemin qui coupe D en M. Considérons le chemin c´ qui est le symétrique de c par rapport à D, jusqu´à M puis égal à c après M. c´ est un chemin reliant ( 0,-2) à ( 20,0). Par ailleurs, tout chemin a´ reliant ( 0,-2) à ( 20,0) coupe D, on peut donc en déduire un chemin a reliant ( 0,0) à ( 20,0) associé à une mauvaise file par la transformation inverse de la précédente. Il y a donc autant de chemins reliant ( 0,0) à ( 20,0) associés à une mauvaise file que de chemins reliant ( 0,-2) à ( 20,0). Or il y a C(9,20) tels chemins ( et non C(6,20) comme je l´avais écrit avant, ça m´apprendra à vouloir réfléchir sans brouillon...) De plus, à chaque mauvais chemin correspond ( 10!)^2 mauvaises files. On a donc :
20!-(10!)^2*C(9,20)=20!/11 bonnes files possibles.
Pfouhhh, ce fut long à écrire...

Voilà j´y suis arrivé mais je vous prévient tout de suite c´est pas très élégant ! Je vais essayer de faire de mon mieux pour vous expliquer ca... néanmoins, il peut y avoir des passages un peu flou, pour vous, car ils sont clairs dans ma tête mais extrèmement long et compliqués à expliquer par écrit. J´espère alors que vous verrez les choses comme moi !

Si vous comprenez et que vous trouvez une manière plus élégante de l´expliquer j´en serais ravi !

Munissez vous d´une feuille et d´un crayon, ce sera nettement plus clair de suivre en dessinant des exemples.

Si on trace le graphe G(p) du nombre de billets de 5 euro encaissés en fonction du nombre de personnes qui ont payé ont obtient une ligne brisée qui, à chaque pas, monte de 1 ou descend de 1. Et de plus on a G(0) = G(20) = 0. On a donc un graphe de longueur 20 qui est " rattaché" à l´axe des abscisses. Une file d´attente est correcte si le graphe G(p) n´est jamais plus petit que 0.
Le problème se transforme donc en un autre problème qui est de compter le nombre de graphes possibles entre les deux sommets fixes ( 0,0) et ( 20,0) et qui ne descendent jamais en dessous de l´axe.

On généralise à une file d´un nombre quelconque pair de personnes, et on décide d´appeler ce nombre 2n-2.
On a donc un graphe de 2n-1 sommets.
J´appelle un graphe de degré k un graphe qui a k points p tels que G(p) = 0 avec 0 < p < 2n-1, j´appelle de tels points des points tangents.
J´appelle un sous-graphe de degré 0 un morceau du graphe allant de a à b tel que G(a) = G(b) = 0 et tel que pour tout c dans ]a,b[ G(c) > 0 ( c-à-d un morceau de graphe compris entre deux points tangents successifs)
On va donc compter indépendamment le nombre de graphes de degré 0, le nbre de graphes de degré 1,..., jusqu´au nombre de graphes de degré n ( voyez-vous pourquoi on ne peut pas avoir un degré suppérieur à n ? ) et les additionner.

Soit P(n) le nombre de graphes possibles pour une situation de 2n-2 personnes. Alors P(1) = 1 ( je sais que c´est un peu bizare... ) .
Il est également évident que P(2) = 1 car la seule possibilité est que celui qui a le billet de 5 passe d´abord.

On peut diviser chaque graphe en sous-graphes de degré nul et de longueur variable.
par exemple la file AABABBABAAABABBABBAB ( A pour monter B pour descendre) se divise en 4 sous-graphes AABABB AB AAABABBABB AB.
Pour compter le nombre de graphes possibles on va compter le nombre de dispositions de sous-graphes possibles.
On voit facilement que le nombre de chemins possibles pour un sous-graphe de degré nul de longueur 2s est P(s-1) c´est-à-dire le nombre de sous-graphes de degré quelconque et de longueur 2s-2 ( vous voyez pourquoi ? )

pour calculer P(n) on additionne les cas de différents degrés en consédérant pour chaque degré les différentes permutions des emplacements des sous-graphes de degré nul
P(1) = 1
P(2) = P(1)
P(3) = P(2) + P(1)P(1) = P(2)P(1) + P(1)P(2)
P(4) = P(3) + P(2)P(1) + P(1)P(2) + P(1)P(1)P(1) = P(3) + P(2)P(1) + P(1) ( P(2) + P(1)P(1)) = P(3)P(1) + P(2)P(2) + P(1)P(3)
P(5) = P(4) + P(3)P(1) + P(2)P(2) + P(1)P(3) + P(2)P(1)P(1) + P(1)P(2)P(1) + P(1)P(1)P(2) + P(1)P(1)P(1)P(1)
= P(4)P(1) + P(3)P(2) + P(2)P(3) P(1)P(4)
.
.
.
http://img301.imageshack.us/my.php?image=formule010pn.jpg

Par récurence jusqu´à P(11) on trouve donc la solution.
Je vous laisse les calculs, j´ai trouvé

P(1) = 1
P(2) = 1
P(3) = 2
P(4) = 5
P(5) = 14
P(6) = 42
P(7) = 132
P(8) = 429
P(9) = 1430
P(10) = 4862
P(11) = 16796

Il y a donc 16796 files possibles qui ne poseront pas de problème

nb en tout il y a 184756 files possible, la probabilité que la caissière n´aie pas d´emmerdes est de 1/11
( remarquez le 11 du P(11)...)

maintenant que je vois ca, je pense qu´il y a surement un moyen plus simple en voyant le problème de facon probabiliste. au flair, j´ai bien l´impression que la probabilité d´avoir une bonne file quand il y a 2p personnes serait de 1/(p+1), mais là il est 2h46 ( je suis chez moi je posterai ca demain matin) et j´ai vraiment plus envie de chercher.

tantale, ca bug ton truc.
On a au total C(10,20) files possibles, c´est à dire 20!/(10!^2) et tu yrouve plus de files non valides que de files toutes catégories...

Bon je ne sais pas si cette solution sera acceptée par le comité... mais si oui c´est à moi de poster une nouvelles énigme non ?

Que diriez-vous de créer un nouveau topic pour ca, avec un nom un peu plus logique que " math?"...
Je vous propose le topic " Rallye Math" que je vais réer à l´instant et sur lequel je poste le problème suivant. ( si l´idée ne vous plait pas, libre à vous de laisser couler mon topic )

Sharkyyy Non, je n´ai pas oublié de reflechir : c´est juste un nbre max de file possible, en considerant 20 pers qui peuvent payer soit avec 5, soit avec 10...

le_duche Envoie un mail au concepteur du site pour que l´on soit sûr de ta reponse

http://perso.wanadoo.fr/marco.butte/problemes/difficiles/ ( c le lien )

Oui mais bon ce que je voulais savoir ct le nombre de file totale possible, soit 184756 d´apres la_duche.
En tout cas, bravo la_duche, la traduction en graphe , fallait y penser

hé non ! le nombre total de files est bien 184756, mais le nombre de files qui ne poseront pas d´emmerdes à la caissière c´est seulement 16796

Oui j´ai bien compris...

pi c´est le_duche et pas la_duche

Ah mince ouai, c parce que douche c feminin lol desole

le_duche : si tu regardes précisément ce que j´ai écrit tu verras que c´est le même raisonnement que toi. Sauf que tu as identifié toutes les personnes ayant un même billet. Ainsi avec n=4 personnes ( A1,A2,B1,B2), tu considères que la file A1,A2,B1,B2 est la même que la file A2,A1,B1,B2 alors que moi non. Ce qui te donne C(10,20) files possibles dans le cas n=20, alors que pour moi il y en a 20!

J´ai pas vraiment regardé ce que tu as fais mais en tous cas ta réponse finale est fausse ! puisqu´elle est suppérieure au nombre total de files...

le_duche : " j´ai pas vraiment regardé ce que tu as fais mais en tous cas ta réponse finale est fausse ! puisqu´elle est suppérieure au nombre total de files..."
%£$&@¤# ! !!! LIS d´abord avant de dire que c´est faux !

Si on différencie TOUTES les personnes ( et non en 2 catégories selon la valeur du billet possédé), il y a 20! files possibles !

ouais ok ton raisonnement est juste et beaucoup plus élégant que le mien
( et pourtant le coup du reflet j´y ai pensé mais j´ai pas exploité...)

Pour généraliser, on a C(2n,n+1) mauvaises files pour 2n personnes, on a C(2n,n) files en général, et donc C(2n,n) - C(2n,n+1) = ( 2n)!/(n!(n+1)!)
Càd 16796 pour 20 personnes.

On doit surement avoir l bonne réponse puisqu´on a des raisonnement complètement différents et la meme réponse

mais on voyais pas la réponse finale de la même manière...