A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

151 personne(s) sur le site en ce moment

E. Cartan

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Théo. Sylow

Théo. Ascoli

Théo. Baire

Loi forte grd nbre

Nains magiques

ETUDE DE LA RECURRENCE :

suivant: RESUME DES RELATIONS DE monter: Boulimie précédent: METHODE :

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.

Cas H(b, r-1)>H(b-1, r) : figure 1.

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

$\includegraphics[width=5.0 in,height=2.86in]{fig1.eps}$

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

et le joueur devra miser m=(H(b,r-1)-H(b-1,r))/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.

Cas H(b, r-1) $\le$ H(b-1, r) : figure 2.

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.

$\includegraphics[width=5.0in,height=2.95in]{fig2.eps}$

$\includegraphics[width=4.23in,height=3.72in]{fig3.eps}$

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

et le joueur devra miser m=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.

Limitation de mise (m $\le$ M) :

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.

Examinons ce cas H(b,r-1)>H(b-1,r)+2M (Figure 3).

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)=H(b-1,r)+M. On a bien alors m=M.

Cas où H(b,r-1)=-1 (branche "perdante" après tirage rouge) :

Pour se trouver dans ce cas, il faut que r>0.

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.

Cas où H(b-1,r)=-1 (branche "perdante" après tirage blanc) :

Pour se trouver dans ce cas, il faut que b>0.

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.

Ceci est illustré sur la figure 4.

$\includegraphics[width=5.0in,height=2.93in]{fig4.eps}$

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

et le joueur devra miser m=(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).

Prise en compte de la limitation de mise (m $\le$ M) :

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.

$\includegraphics[width=2.25in,height=2.06in]{fig5.eps}$