Les-Mathematiques.net - Cours de mathématiques supérieures

Existe-t-il une ou des stratégies permettant à un joueur de gagner à coup sûr au jeu suivant ?

Le joueur sort de sa poche un montant fixé à (h) unités de monnaie et les donne au croupier ( h est positif ou nul). Cet handicap initial n'est donné qu'une seule fois au début du jeu.

Le joueur annonce, à haute et intelligible voix, un nombre (m) supérieur à 0 et inférieur ou égal à un maximum (M) fixé.

Le joueur a en poche une somme supérieure à (r.M+h), ce qui lui permettrait donc d'annoncer M à chaque fois s'il le voulait.

Une boule est tirée au hasard ( par la main du croupier, dont le nom est Monsieur Hasard). Cette boule n'est pas remise dans l'urne.

Si la boule tirée est rouge, le joueur sort de sa poche (m) unités de monnaie et les donne au croupier.

Si la boule tirée est blanche, le croupier donne au joueur (m) unités de monnaie.

Si, à un certain moment, le joueur a récupéré plus d'argent qu'il n'en a sorti au total (ne serait-ce que d'une unité), il est déclaré GAGNANT, la partie est terminée (et le joueur devient propriétaire du casino !).

Si au contraire, à la fin du jeu (lorsqu'il n'y a plus de boule dans l'urne) le joueur n'a pas récupéré au moins autant d'argent qu'il en a déboursé, il est déclaré PERDANT (et il est totalement dépouillé, au point de sortir du casino nu comme un ver).

Le dilemme auquel le joueur doit faire face est le suivant : Il connaît au départ les nombres : r, b, h et M. Doit-il accepter la partie ? Pour cela, il veut savoir s'il peut, ou non, gagner à coup sûr.

Un exemple d'un tel problème a été posé avec les données suivantes : r=200, b=100, h=0 et M=1500.

METHODE :

Nous allons le traiter d'un façon très générale, par une méthode que l'on pourrait qualifier de récurrence. En fait, il s'agit d'un "arbre de décisions" qui se ramifie pour chaque possibilité de choix : choix de (m) par le joueur, et "choix" de la couleur de boule par le hasard (mais, plus exactement, par le croupier, Monsieur Hasard, qui n'est pas très honnête).

Etant donné r, b et M fixés, le résultat dépend du handicap (h). On conçoit que si h est grand, le joueur ne pourra pas gagner. Pour h suffisamment petit, dans certaines conditions il deviendra possible de gagner à coup sûr. Soit H(b,r) la valeur de h se situant à la limite entre ces deux cas :

Si 0 $\le$ h $\le$ H(b,r), il existe au moins une stratégie pour gagner à coup sûr.

Convention : Si H(b,r)<0, il faudrait que h soit négatif pour pouvoir gagner, ce qui n'est pas envisagé dans la présente étude. Ainsi, H(b,r)<0 signifie que la branche correspondante de l'arbre de décision est une branche "perdante".

Par convention, toutes les branches "perdantes" seront repérées par H(b,r)= -1 (ce qui est sans incidence sur les résultats puisque la branche correspondante est "perdante", quel que soit la valeur négative).

Si on connaît H(b,r), on peut répondre à la question posée à la première ligne.

Observation importante : L'intérêt du joueur est que h soit le plus petit possible et H(b,r) le plus grand possible. En effet, pour gagner à coup sûr, il faut que h $\le$ H(b,r).

Au contraire, l'intérêt de Monsieur Hasard est que h soit le plus grand possible et H(b,r) le plus petit possible. En effet, pour que le joueur ne puisse pas gagner à coup sûr, il faut que h>H(b,r).

ETUDE DE LA RECURRENCE :

Supposons que le problème a été résolu dans le cas de [b, (r-1)], c'est à dire que l'on suppose que H(b, r-1) est connu et qu'il ait aussi été résolu pour le cas [(b-1), r], c'est à dire que l'on suppose que H(b-1, r) est connu.

Pour que le joueur soit sûr de gagner, il faut que, quelle que soit la couleur tirée, la branche de l'arbre de décision correspondante soit gagnante à coup sûr.

Considérons d'abord un exemple de situation "gagnante". Pour un handicap (h) et une mise (m), si une boule blanche est tirée, le joueur gagne (m) et son handicap pour le coup suivant se trouve réduit à (h-m) : c'est le point P $_{b}$ . Il reste (b-1) boules blanches et (r) rouges. La condition pour que le joueur gagne est (h-m) $\le$ H(b-1,r).

Si une boule rouge est tirée, le joueur perd (m) et son handicap pour le coup suivant se trouve porté à (h+m) : c'est le point P $_{r}$ . Il reste (b) boules blanches et (r-1) rouges. La condition pour que le joueur gagne est (h+m) $\le$ H(b,r-1).

On voit bien sur la figure que le joueur doit annoncer une mise comprise entre m $_{b}$ et m $_{r}$ . S'il suit cette stratégie, quel que soit le tirage blanc ou rouge, Pr n'est pas au dessus de la barre H(b-1,r) et Pb n'est pas au dessus de la barre H(b,r-1), donc le joueur sera gagnant.

Cherchons maintenant quelle est la valeur maximum de h qui laisse au joueur la possibilité d'être gagnant. Lorsque h augmente, la plage m $_{b} \le$ m $\le$ m $_{r}$ se restreint, jusqu'à ne devenir qu'un point m $_{b}$ =m=m $_{r}$ =(H(b,r-1)-H(b-1,r))/2 : Figure 1, cas h maximum. Pour cet handicap maximum, le joueur est encore gagnant. Ceci correspond à la définition de H(b,r). Par conséquent : H(b,r)=(H(b-1,r)+H(b,r-1))/2

Il se peut que (H(b-1,r)+H(b,r-1)) ne soit pas un nombre pair. Pour être sûr de gagner, il faut que h soit inférieur ou égal à la valeur entière inférieure. Si (H(b-1,r)+H(b,r-1)) est impair, alors H(b,r) = l'entier immédiatement inférieur à (H(b-1,r)+H(b,r-1))/2.

On constate aisément que la mise (m) peut indifféremment être arrondie à l'entier inférieur ou supérieur à (H(b,r-1)-H(b-1,r))/2.

Pour vérification, la figure 1, "cas perdant" montre que si h>H(b,r), il est impossible de gagner à coup sûr. Si le joueur mise m $_{1}$ <m $_{r}$ , M.Hasard tirera une boule blanche et le point P $_{b}$ sera au dessus de la barre H(b-1,r) donc cas perdant. Si le joueur mise m $_{3}$ >m $_{b}$ , M.Hasard tirera une boule rouge et le point P $_{r}$ sera au dessus de la barre H(b,r-1) donc cas perdant. Si le joueur mise m $_{r}$ <m $_{2}$ <m $_{b}$ , M.Hasard peut tirer ce qu'il veut, les deux point sont au dessus de leur barre respective, donc cas toujours perdant. Ceci confirme que H(r,b) est bien la valeur qui a été trouvée.

Quelle que soit la mise (m), M.Hasard tirera le rouge, de telle sorte que Pr tende à être au dessus de la barre H(b,r-1).

La barre H(b-1,r) a été représentée sur la figure, mais elle n'intervient donc pas.

Pour que le joueur se place sur une branche gagnante il faut que P $_{r}$ ne soit pas au dessus de la barre H(b,r-1). Il est nécessaire que h ne soit pas plus grand que H(b,r-1) et le joueur devra miser m $\le$ m $_{r}$ .

Cherchons quelle est la valeur maximum de h qui laisse au joueur la possibilité d'être gagnant. Lorsque h augmente, m $_{r}$ diminue et la plage dans laquelle le joueur doit miser se restreint, jusqu'à ne devenir qu'un point m=m $_{r}$ =1, puisque la mise ne doit pas être inférieure à 1 : Figure 2, cas h maximum. Pour cet handicap maximum, le joueur est encore gagnant. Ceci correspond à la définition de H(b,r). Par conséquent : H(b,r)=H(b,r-1)-1

Pour vérification, la figure 2, "cas perdant" montre que si h>H(b,r), il est impossible de gagner à coup sûr. Que le joueur mise m $_{1}$ ou m $_{2}$ , M.Hasard tirera une boule rouge et le point P $_{r}$ sera au dessus de la barre H(b,r-1) donc ce cas est perdant pour le joueur.

Dans ce qui précède, la condition m $\le$ M n'a pas été prise en compte. Cette condition ne serait pas respectée dans le cas H(b, r-1)>H(b-1, r) : figure 1 et si m=(H(b,r-1)-H(b-1,r))/2 > M.

Pour m=M, la valeur de h maximum permettant encore au joueur de gagner à coup sûr est H(b,r)=H(b-1,r)+M. On a bien alors m=M.

Il est évident que M.Hasard tirera une boule rouge pour que le joueur soit engagé sur la branche perdante. Donc H(b,r)=-1.

La première idée est de penser que M.Hasard tirera une boule blanche pour que le joueur soit engagé sur la branche perdante. Mais si le joueur a choisi (m) assez grand, g=(m-h) sera positif et le joueur aura récupéré plus d'argent qu'il n'en a sorti au total : il sera gagnant juste avant d'être engagé dans la branche perdante.

Si m $_{g} \quad \le$ m<m $_{r}$ , et si rouge est tiré, P $_{r}$ est au dessous de la barre H(b,r-1). Si blanc est tiré, Pb passe dans le domaine des gains positifs (g $\ge$ 0) et la partie est immédiatement terminée avec le joueur gagnant.

Si m=m $_{1}$ <m $_{g}$ , la partie n'est pas terminée (Pb au dessus le la barre -1) et le joueur est engagé sur la branche perdante.

Si m>m $_{r}$ , M.Hasard joue rouge, Pr est au dessus de la barre H(b,r-1) et le joueur sera perdant.

Plus h est grand, plus l'intervalle m $_{g} \quad \le$ m<m $_{r}$ est restreint, jusqu'à devenir un point m=m $_{g}$ (Figure 4, cas "gagnant" h maximum). Pour cet handicap maximum, le joueur est encore gagnant. Ceci correspond à la définition de H(b,r). Par conséquent : H(b,r)=(H(b,r-1)-1)/2

Pour vérification, la figure 4, "cas perdant" montre que si h>H(b,r), il est impossible de gagner à coup sûr. Que le joueur mise m $_{1}$ ou m $_{2}$ , M.Hasard tirera une boule blanche et le joueur se trouve engagé sur la branche (B) perdante. Si le joueur mise m $_{3}$ , M.Hasard tire rouge, le point P $_{r}$ est au dessus de la barre H(b,r-1).

Pour avoir le droit de miser m=(H(b,r-1)+1)/2, il faut que cette valeur ne soit pas plus grande que M. Que se passe-t-il lorsque H(b,r-1)>2M-1 ? (Figure 5). Les lignes pointillées rappellent le cas sans limitation de mise.

Pour m=M, la valeur de h maximum permettant encore au joueur de gagner à coup sûr est H(b,r)=M-1.

RESUME DES RELATIONS DE RECURRENCE :

Le tableau suivant rassemble les relations de la récurrence permettant de trouver H(b,r) connaissant H(b-1,r) et H(b,r-1).

n	Cas :	H(b,r) =	m =
(1)	H(b,r-1)=-1 , r>0	-1	Branche perdante
(2)	H(b-1,r)=-1 , b>0 et H(b,r-1)>2M-1	M-1	M
(3)	H(b-1,r)=-1 , b>0 et H(b,r-1) $\le$ 2M-1	(H(b,r-1)-1)/2 (*)	(H(b,r-1)+1)/2 (*)
(4)	H(b, r-1) $\le$ H(b-1, r), r et b > 0	H(b,r-1)-1	1
(5)	H(b-1,r)+2M<H(b,r-1), r et b > 0	H(b-1,r)+M	M
(6)	H(b-1,r)<H(b,r-1) $\le$ H(b-1,r)+2M et r, b>0	(H(b,r-1)+H(b-1,r))/2	(H(b,r-1)-H(b-1,r))/2 (*)
		(*) : si non entier, arrondir à l'entier inférieur.

INITIALISATION DE LA RECURRENCE :

Cas 1 boule blanche et 0 boule rouge : Le joueur choisi évidemment m=M. Il gagne la partie si h<M. Il perd si h $\ge$ M. Donc H(1,0)=M-1.

Cas de b boules blanches et 0 boules rouges : Le joueur choisi évidemment m=M à chaque tirage. Il gagne la partie si h<b.M. Il perd si h $\ge$ b.M. Donc H(b,0)=b.M-1.

Cas 0 boule blanche et 1 boule rouge : Si le joueur à atteint cette situation sans terminer avant (en gagnant la partie), il a forcément perdu. C'est l'extrémité d'une branche perdante, que l'on repère donc par H(0,1)= -1 , selon notre convention (Si les handicaps négatifs étaient permis, ce serait -2, mais il faudrait revoir certaines des relations précédentes. Ainsi que décidé au début, nous avons exclu de l'étude le cas des handicaps négatifs).

Cas 0 boule blanche et r boule rouge : de même que pour le cas précédent et à fortiori, la branche est perdante. H(0,r)= -1.

EXEMPLE : Calcul de H(1,1)

b=1, r=1 ; H(b-1,r)=H(0,1)=-1 ; H(b,r-1)=H(1,0)=M-1. C'est le cas n 3 du tableau (H(b,r-1)-1)/2=(M-2)/2

Ceci signifie que, dans ce cas r=1, b=1 et M=1500, l'handicap ne doit pas être supérieur à 749 pour que le joueur soit sûr de gagner.

Si blanc est tiré, il gagne immédiatement. Si rouge est tiré, il se retrouve avec un handicap égal au h précédent plus m, soit h=750+749=1499 au maximum. Pour le coup suivant, H(1,0)=M-1=1499. On voit que h=1499 et H=1499 satisfont bien à la condition h $\le$ H. Donc le joueur gagne (il annonce m=M=1500).

Bien entendu, c'est l'exemple le plus élémentaire, dont la solution était évidente à priori.

RESULTATS :

b=	nombre de boules rouges r =
	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	749	374	186	92	45	22	10	4	1	0	-1	-1	-1	-1
2	1874	1124	655	373	209	115	62	33	17	8	3	1	0	-1
3	3186	2155	1405	889	549	332	197	115	66	37	20	10	5	2
4	4592	3373	2389	1639	1094	713	455	285	175	106	63	36	20	11
5	6045	4709	3549	2594	1844	1278	866	575	375	240	151	93	56	33
6	7522	6115	4832	3713	2778	2028	1447	1011	693	466	308	200	128	80
7	9010	7562	6197	4955	3866	2947	2197	1604	1140	807	557	378	253	166
8	10504	9033	7615	6285	5075	4011	3104	2354	1751	1279	918	648	450	308
9	12001	10517	9066	7675	6375	5193	4148	3251	2501	1890	1404	1026	738	523
10	13500	12008	10537	9106	7740	6466	5307	4279	3390	2640	2022	1524	1131	827
11	14999	13503	12020	10563	9151	7808	6557	5418	4404	3522	2772	2148	1639	1233
12	16499	15001	13510	12036	10593	9200	7878	6648	5526	4524	3648	2898	2268	1750
13	17999	16500	15005	13520	12056	10628	9253	7950	6738	5631	4639	3768	3018	2384
14	19499	17999	16502	15011	13533	12080	10666	9300	8023	6827	5733	4750	3884	3134

Avec 1 boule blanche, le joueur est sûr de gagner s'il y a moins de 11 boules rouges.

Avec 2 boules blanches, le joueur est sûr de gagner s'il y a moins de 14 boules rouges.

Avec 3 boules blanches, le joueur est sûr de gagner s'il y a moins de 16 boules rouges.

Avec 10 boules blanches, le joueur est sûr de gagner s'il y a moins de 29 boules rouges.

Avec 15 boules blanches, le joueur est sûr de gagner s'il y a moins de 37 boules rouges.

Avec 20 boules blanches, le joueur est sûr de gagner s'il y a moins de 44 boules rouges.

Avec 30 boules blanches, le joueur est sûr de gagner s'il y a moins de 58 boules rouges.

Avec 40 boules blanches, le joueur est sûr de gagner s'il y a moins de 72 boules rouges.

Avec 50 boules blanches, le joueur est sûr de gagner s'il y a moins de 84 boules rouges.

Avec 60 boules blanches, le joueur est sûr de gagner s'il y a moins de 97 boules rouges.

Avec 70 boules blanches, le joueur est sûr de gagner s'il y a moins de 109 boules rouges.

Avec 80 boules blanches, le joueur est sûr de gagner s'il y a moins de 121 boules rouges.

Avec 90 boules blanches, le joueur est sûr de gagner s'il y a moins de 133 boules rouges.

Avec 100 boules blanches, le joueur est sûr de gagner s'il y a moins de 145 boules rouges.

Avec 100 boules blanches et 200 rouges, le joueur ne peut pas être sûr de gagner.

Au contraire, si M.Hasard ne joue pas au hasard, le joueur est certain de perdre la partie.

Pour que le joueur soit sûr de gagner s'il y a 200 boules rouges, il faudrait qu'il y ait au moins 148 boules blanches.

Remarque : Il faut bien comprendre que ce sont les conditions pour que le joueur soit certain de gagner et que le problème serait complètement différent s'il jouait plusieurs parties en acceptant d'en perdre quelques unes. Il faudrait alors qu'il ne vise pas un gain de une unité au moins à chaque partie. Il faudrait avoir pour objectif le gain moyen maximum. Il est évident qu'avec par exemple 100 boules blanches et 200 rouges et la mise limitée à 1500, l'espérance moyenne de gain serait positive et probablement élevée.

Cas type de test de stratégie : Le cas suivant particulièremement intéressant: b=20, r=40, M=430 et h=0. Avec ces conditions initiales, les chances du joueur et celles de M. Hasard sont presque équilibrées ( avec un avantage minimum pour le joueur ). Contre l'ordinateur, le joueur peut encore gagner à coup sûr, mais à condition de ne commettre pas une seule faute tout au long de la partie.

DISCUSSION SUR LA VALIDITE DE LA DEMONSTRATION :

La démonstration comprend une partie théorique et une partie par calcul numérique.

Bien évidemment, chacune doit être refaite par des vérificateurs indépendants, car nul n'est à l'abri d'une erreur, aussi bien dans les développements analytiques que dans la construction de l'algorithme et la programmation. Ceci n'a rien d'anormal et l'on voit de plus en plus fréquemment des preuves qui font intervenir des calculs par ordinateur.

J'espère que plusieurs personnes voudrons bien s'atteler à cette tâche ingrate et de préférence en s'y prenant de manières différentes, pour une confirmation solide.

De toutes façon, même s'il y a une ou des erreurs qui affecteraient les résultats précédents, cela ne me gênerait pas du tout : Un démonstration parfaite en tout point finirait bien par en ressortir. L'essentiel pour moi, dans ce papier, est d'expliquer le principe de la démarche (finalement assez simple et surtout très abordable en ce qui concerne les calculs numériques). Cette méthode permet de répondre à la question posée et d'une façon encore plus générale qu'espéré au départ.

Je remercie Monsieur Daniel Serres ( qui est à l'origine du problème posé ) pour ses encouragements et pour les vérifications expérimentales qu'il conduit actuellement avec le logiciel ``Boulimie v2-0.exe''( Jeu téléchargeable. Attention ne fonctionne correctement qu'avec un écran dimensionné en 1024 par 768 pixels ). Je remercie également les personnes ayant participé à des vérifications ( encore partielles à ce jour ) de la théorie exposée dans le présent article.