Démo qui tue ============ Notations --------- M: mise maximale autorisée r: nombre de boules rouges restantes b: nombre de boules blanches restantes Introduction ------------ Pour plus de commodité, on suppose que le capital de départ est -1, et le but est donc d'arriver à 0. On note C(r,b) le capital minimal nécessaire pour être sûr de gagner la partie avec r boules rouges et b boules blanches. S'il ne reste plus de boules blanches, alors le capital minimal est 0 puisqu'après on ne peut plus gagner. D'où pour tout r, C(r,0) = 0 S'il ne reste plus de boules rouges, on est sûr de tirer une blanche à chaque fois, et donc on va miser M, la mise maximale, pour gagner le plus possible. D'où pour tout b, C(0,b) = -bM Extension des règles -------------------- On va rendre les règles moins strictes, et permettre de miser n'importe quelle somme sans limitation, même non-entière et négative, s'il reste au moins une boule de chaque couleur. Donc le capital pourra lui aussi être non-entier. On notera que cette hypothèse ne remet pas en cause le calcul de C(0,b) et de C(r,0) puisqu'elle n'est valable que si b!=0 et r!=0. Si l'on arrive à montrer qu'il est impossible de gagner avec l'extension des règles, alors c'est une preuve suffisante qu'il est impossible de gagner sans l'extension des règles. La réciproque est bien entendu fausse, mais j'en ai rien à battre puisque mon but est justement de montrer que l'on ne peut pas gagner. Démonstration ------------- Le but est de calculer C(200,100). On va donc calculer C(r,b) pour r et b tous deux non-nuls. Comme C(r,b) est le capital minimal nécessaire pour gagner, on peut l'exprimer en fonction de C(r-1,b) et C(r,b-1). Il s'agit du plus petit c possible tel qu'il existe une mise m(c) vérifiant : c + m >= C(r,b-1) (en cas de boule blanche tirée) c - m >= C(r-1,b) (en cas de boule rouge tirée) Une résolution graphique amène trivialement : C(r,b) = 1/2 ( C(r,b-1) + C(r-1,b) ) La mise optimale correspondante est alors 1/2 ( C(r,b-1) - C(r-1,b) ) Le problème se résume donc à calculer C(200,100), qu'on peut calculer numériquement bien sûr, mais c'est quand-même beaucoup plus rigolo d'en calculer une expression générale en fonction de r et b. On est pas non plus des ptites bites, merde, quoi. On introduit U = C / M parce que ça va rendre les calculs plus simples, on a alors : U(r,0) = 0 U(0,b) = -b U(r,b) = 1/2 ( U(r,b-1) + U(r-1,b) ) pour r!=0 et b!=0 Calculons U(r,1) parce que ça a l'air facile : U(r,1) = 1/2 ( U(r,0) + U(r-1,1) ) 2 U(r,1) = 0 + U(r-1,1) 2^r U(r,1) = U(0,1) = -1 U(r,1) = -1 / 2^r Maintenant calculons U(r,2) pour voir ce que ça donne : U(r,2) = 1/2 ( U(r,1) + U(r-1,2) ) 2 U(r,2) = - 1/2^r + U(r-1,2) 2^r U(r,2) = - 1/2 + 2^(r-1) U(r-1,2) 2^r U(r,2) = - r/2 + U(0,2) 2^r U(r,2) = - r/2 - 2 U(r,2) = - (2 + r/2) / 2^r U(r,2) = - (r + 4) / 2^(r+1) Hypothèse de récurrence : U(r,b) = - Fb(r) / 2^(r+b-1) où Fb est une fonction exprimée en fonction de F(b-1), donc en fonction de b et de F0. On effectue donc une récurrence sur b, avec des égalités valables pour tout r. Admettons que ce soit valable jusqu'au rang b-1. U(r,b) = 1/2 ( U(r,b-1) + U(r-1,b) ) 2 U(r,b) = - F(b-1)(r) / 2^(r+(b-1)-1) + U(r-1,b) 2^r U(r,b) = - F(b-1)(r) / 2^(b-1) + 2^(r-1) U(r-1,b) 2^r U(r,b) = U(0,b) - sigma(i=1,r,F(b-1)(i)) / 2^(b-1) 2^r U(r,b) = - b - sigma(i=1,r,F(b-1)(i)) / 2^(b-1) U(r,b) = - ( b.2^(b-1) + sigma(i=1,r,F(b-1)(i)) ) / 2^(r+b-1) U(r,b) = - Fb(r) / 2^(r+b-1) CQFD. avec Fb(r) = b.2^(b-1) + sigma(i=1,r,F(b-1)(i)) Il est très difficile d'exprimer Fb en fonction de b de manière simple, mais on s'aperçoit qu'il s'agit d'une fonction polynôme de degré b-1. Ça nous fait une relativement belle jambe, je vous l'accorde. Les premières expressions de Fb sont : F0(r) = 0 F1(r) = 1 F2(r) = 2.2^1 + sigma(i=1,r,F1(i)) F2(r) = 4 + r F3(r) = 3.2^2 + sigma(i=1,r,F2(i)) = 12 + 4r + r(r+1)/2 F3(r) = 12 + 9/2 r + 1/2 r^2 F4(r) = 4.2^3 + sigma(i=1,r,F3(i)) = 32 + 12r + 9/2 r(r+1)/2 + 1/2 r(r+1)(2r+1)/6 = 32 + 12r + 9/4 r + 9/4 r^2 + 1/6 r^3 + 1/6 r^2 + 1/12 r^2 + 1/12 r F4(r) = 32 + 43/3 r + 5/2 r^2 + 1/6 r^3 Je pense qu'on arrive aux limites de l'expression littérale. Pour la suite, il va falloir utiliser une résolution numérique. On va utiliser Scheme parce que c'est un langage qui torche pas mal pour des problèmes récursifs : Résolution numérique -------------------- ; build F0 (define F0 (lambda (r) (if (zero? r) '(0) (append '(0) (F0 (- r 1)))))) ; calculate 2^x (define p2 (lambda (x) (if (zero? x) 1 (* 2 (p2 (- x 1)))))) ; sw - used by inner-Fb->Fb+1 (define sw (lambda (l) (if (null? l) () (append (sw (cdr l)) (list (car l)))))) ; inner-Fb->Fb+1 - used by Fb->Fb+1 (define inner-Fb->Fb+1 (lambda (Fb Fb+1) (if (null? Fb) (sw Fb+1) (inner-Fb->Fb+1 (cdr Fb) (append (list (+ (car Fb) (car Fb+1))) Fb+1))))) ; Fb->Fb+1 - get Fb+1 from Fb and b (define Fb->Fb+1 (lambda (Fb b) (inner-Fb->Fb+1 (cdr Fb) (list (* (+ b 1) (p2 b)))))) ; calculate Fb - r is used as a boundary (define Fb (lambda (b r) (if (zero? b) (F0 r) (Fb->Fb+1 (Fb (- b 1) r) (- b 1))))) ; calculate Fb(r) (define F (lambda (b r) (list-ref (Fb b r) r))) Voilà, c'est tout. On peut maintenant vérifier avec quelques valeurs qu'on a bien un programme qui calcule Fb, puis calculer F100(200) : > (Fb 0 10) (0 0 0 0 0 0 0 0 0 0 0) ; on a F0(r) = 0 par construction > (Fb 1 10) (1 1 1 1 1 1 1 1 1 1 1) ; on a bien F1(r) = 1 > (Fb 2 10) (4 5 6 7 8 9 10 11 12 13 14) ; on a bien F2(r) = 4 + r > (Fb 3 10) (12 17 23 30 38 47 57 68 80 93 107) ; on a bien F3(r) = 12 + 9/2 r + 1/2 r^2 > (F 100 200) 7660417277820735421177197226927116492957112320976609738148295105818826475069008800 On obtient une valeur inférieure à 2^273. On en déduit donc : U(r,b) = - Fb(r) / 2^(r+b-1) U(200,100) = - F100(200) / 2^(200+100-1) U(200,100) > - 2^273 / 2^299 U(200,100) > - 1 / 67108864 Or on a posé U = C / M, donc : C(200,100) > - 1500 / 67108864 > -1 Le capital de départ est donc nécessairement strictement supérieur à -1 pour qu'il existe un moyen de gagner quel que soit le tirage. Or on a pris pour hypothèse un capital de départ égal à -1, ce qui signifie qu'il n'existe pas de moyen de gagner quel que soit le tirage avec l'extension des règles. Conclusion ---------- Puisqu'on a montré qu'il n'était pas possible de gagner avec l'extension des règles, on en déduit donc qu'il n'est pas possible de gagner avec les règles de départ, puisqu'une stratégie pour gagner avec les règles de départ serait aussi valide avec les règles étendues. DTC.