Les patiences sont un stimulant prétexte pour faire des raisonnements stratégiques et des calculs probabilistes.
Article réservé aux abonnés numériques
En cas de confinement total avec interdiction de s’approcher de quiconque et si tous les réseaux et ordinateurs tombent en panne, il vous restera la lecture, le dessin, le bricolage et… les patiences, aussi dénommées solitaires ou réussites.
Ces jeux avec des pions ou des cartes se jouent seul. Après une série de manipulations selon les règles de la patience, vous serez gagnant ou perdant. Il y a deux catégories de patiences. Les patiences « déterministes » ou « automatiques » sont celles où vous devez simplement suivre des règles parfaitement précises ne vous laissant aucun choix. À l’opposé, les patiences « stratégiques » présentent des situations où plusieurs actions sont possibles et qui, selon vos choix, vous conduiront à gagner ou à perdre.
Pour les patiences déterministes, le hasard intervient avant le début du jeu et provient de l’ordre initial des cartes du paquet : le mécanisme d’une patience déterministe vous conduit à la victoire ou à la défaite, celle-ci étant fixée par avance et cachée dans le paquet dès le début des manipulations, qui ne font que la décoder.
Les patiences stratégiques incitent à réfléchir pour trouver la meilleure façon de jouer. Nous donnerons des exemples de patiences stratégiques dont on peut trouver la stratégie optimale de jeu. Les patiences déterministes semblent sans intérêt, puisqu’elles reviennent à tirer à pile ou face « partie gagnée » ou « partie perdue ». Sauf que ce n’est pas vraiment comme un tirage à pile ou face puisqu’on ignore quelle est la probabilité de gagner. C’est là que se trouve l’intérêt de ces patiences. Évaluer la probabilité de gagner peut être difficile et l’ordinateur est souvent indispensable pour effectuer le calcul.
Les réussites envisagées ici sont aussi simples que possible et, d’ailleurs, seule la couleur « noire » ou « rouge » des cartes y aura de l’importance. Les maîtriser occupe un bon moment, ce qui prouve que même des jeux à l’apparence idiote ont un intérêt pour l’amateur curieux et mathématicien.
La patience « N’en garder qu’une » est d’une simplicité extrême. Y jouer et la proposer à des élèves pour qu’ils devinent comment gagner est un exercice intéressant dès la classe de sixième.
On prend un jeu de cartes quelconques bien battu et on étale en ligne 8 cartes ou plus dont seules les couleurs rouge (R) ou noire (N) sont importantes. Par exemple :
Quelles sont les règles ? À chaque étape, on déplace au choix un paquet de cartes dont la couleur de la carte supérieure est différente de la carte supérieure du paquet à sa gauche ; on pose le paquet sélectionné sur celui à sa gauche. Les paquets restants sont alors resserrés. On dit qu’on « replie » la ligne. Pour gagner, il faut tout replier en un seul paquet.
Avec notre exemple, on commence avec la ligne :
En partant de la gauche, on prend la dernière carte et on la place au-dessus sur l’avant-dernière, ce qui est autorisé puisque ces deux cartes sont de couleurs différentes :
Un second mouvement consiste à prendre l’avant-dernière carte et à la placer sur celle à sa gauche :
On poursuit par exemple de cette façon :
Arrivé à ces quatre paquets, on ne peut plus rien faire et on a perdu, puisqu’il fallait aboutir à un seul paquet. Avec la configuration initiale de l’exemple, il y a une façon de réussir… que je vous laisse chercher.
Deux questions générales se posent. Quelle est la meilleure façon de jouer ? Et si on l’utilise, quelle est alors la probabilité de gagner ? Des réponses viennent assez rapidement.
Situations perdantes. Il est évident que si la ligne se termine par deux cartes ou plus de la même couleur, il sera impossible d’arriver à un seul paquet, car chaque manipulation maintiendra identique les cartes au-dessus des deux derniers paquets, qui ne pourront donc jamais se replier en un seul.
Situations gagnantes et stratégie. Si les deux dernières cartes de la ligne sont de couleurs différentes, on utilise la méthode suivante qui permet de gagner à coup sûr. On se sert de l’avant-dernière carte et de celles de la même couleur pour faire disparaître toutes les cartes de couleur opposée en procédant de la droite vers la gauche. L’avant-dernière carte est utilisée pour recouvrir toutes les cartes de couleur opposée qui la précèdent. Puis la carte de la même couleur placée à sa gauche est utilisée de même, et ainsi de suite. Une fois qu’il ne reste que la dernière carte et des cartes de couleur opposée à sa gauche, on utilise cette dernière carte pour recouvrir toutes les autres une à une. On a alors un paquet unique.
Une condition nécessaire et suffisante pour avoir la possibilité de gagner est donc que les deux dernières cartes soient de couleur différentes.
La probabilité d’avoir la possibilité de gagner est donc la probabilité que les deux dernières cartes soient (R, N) ou (N, R). Si le paquet utilisé pour composer la ligne de départ possède r cartes rouges et n cartes noires, cette probabilité est :
r/(r + n) × n/(r + n – 1) + n/(n + r) × r/(n +r – 1) = 2rn/((n + r)(n + r - 1)).
Avec un jeu de 32 cartes (16 R, 16 N), cela donne 2 × 16 × 16/(32 × 31) = 51,61 %, ce qui est plutôt satisfaisant !
Envisageons maintenant des variantes dont l’analyse complète est encore possible. Pour la variante « En garder deux de la même couleur », les règles sont les mêmes, mais le but est d’arriver à avoir exactement deux paquets de la même couleur à la fin des repliements. Voici le résultat. On peut gagner si et seulement si : « Il y a au moins une autre carte ayant la même couleur que la dernière, et la ligne ne se termine pas par plus de deux cartes de la même couleur ».
Nous vous laissons le plaisir de découvrir la stratégie gagnante.
Dans le cas où il faut garder deux cartes de la même couleur, le calcul de la probabilité de gagner est encore assez simple. Pour ce faire, calculons d’abord la probabilité des mauvais cas. Il y en a de deux sortes.
Ces quatre situations (a1, a2, b1, b2) sont disjointes : il est impossible d’en avoir deux en même temps. Donc la probabilité des mauvais cas est la somme des probabilités de chacune de ces situations. On calcule la probabilité de chacune en considérant les cartes de la dernière à la première. En supposant que les lignes sont de longueur 10 et qu’il y a au moins 8 rouges et 8 noires dans le paquet de cartes utilisé, les probabilités sont les suivantes.
Pour le jeu de 32 cartes, cela donne 70 211/310 151 = 0,226 373 90. La probabilité de gagner en jouant bien est donc de 77,3626 %. C’est trop facile !
Nous maîtrisons maintenant bien les règles pour aborder la variante générale de cette patience. On se donne un entier K (par exemple choisi au hasard en lançant un dé) et une ligne de L cartes et on cherche à replier la ligne en K paquets de la même couleur. L’analyse va conduire à une condition nécessaire et suffisante pour qu’on puisse arriver à K paquets de la même couleur. On note d’abord trois cas où il est évident qu’on ne peut pas réussir.
Un petit travail de réflexion conduit alors à imaginer une stratégie qui, si l'on n’est pas dans l'un des trois cas impossibles, fait gagner à coup sûr.
La probabilité de gain devient plus compliquée à calculer. Pour faciliter le calcul, on suppose que le paquet de cartes est infini et qu’à chaque fois qu’on prend une carte, elle a 50 % de chances d’être rouge et 50 % de chances d’être noire, ce qui revient au même que de supposer que les couleurs des cartes de la ligne initiale sont tirées R ou N à l’aide d’une pièce de monnaie (pile = R, face = N).
Voici les résultats du calcul, que nous ne détaillons pas, avec une ligne de 10 cartes au départ. On remarquera que les résultats pour K = 1 et K = 2 ne sont pas exactement ceux qu’on a trouvés plus haut, mais qu’ils en diffèrent très peu. C’est normal, car omettre de prendre en compte la légère variation des probabilités due à l’absence des cartes déposées ne change pas grand-chose.
La probabilité P de pouvoir arriver à K paquets (c’est-à-dire de ne pas se trouver dans l'un des trois cas impossibles) est :
On voit que la probabilité de gagner (en utilisant la bonne stratégie) est maximale pour K = 3. Si l'on vous demande quelle valeur de K vous allez chercher à atteindre, il faut donc répondre 3. Si le K est choisi au hasard avec un dé, la probabilité de réussir pour celui qui applique la stratégie optimale est la moyenne des six premières probabilités, qui est égale à 0,6917.
Venons-en à un second exemple un peu plus coriace. Il s’agit d’une patience déterministe n’utilisant que le rouge et le noir. Là encore, malgré sa simplicité apparente, le calcul de la probabilité de gagner semble contraindre à utiliser l’ordinateur ou à mener des raisonnements délicats.
On utilise un paquet de L cartes contenant un nombre pair de cartes rouges et un nombre pair de cartes noires. On prend les cartes une à une sur le dessus du paquet qu’on tient en main, les faces vers le dessous. On constitue deux paquets de cartes sur la table devant soi, l'un à gauche, l'un à droite. Si les deux paquets ont le même nombre de cartes ou si celui de gauche a moins de cartes que celui de droite, la nouvelle carte va à gauche, sinon elle va à droite. Après chaque nouvelle carte posée, on regarde si les cartes du dessus des deux paquets sont de la même couleur ; si c’est le cas, on les enlève. On regarde à nouveau si les cartes du dessus des paquets sont de la même couleur ; si c’est le cas on les enlève, etc. Quand on ne peut plus rien enlever, on prend la carte du dessus du paquet qu’on tient en main et on la pose sur l’un des deux paquets comme indiqué plus haut.
Le but est que les deux paquets soient vides une fois posée la dernière carte du paquet qu’on tient en main et opérés les retraits qu’elle permet.
On tient en main un paquet de cartes, par exemple R/N/R/R/N/R/N/N, on prend les cartes une à une et on en fait deux paquets sur la table ; on commence toujours le paquet à gauche et on égalise la taille des paquets quand c’est nécessaire. Lorsque les cartes au sommet des paquets sont de la même couleur, on les enlève. Le but est d’obtenir deux paquets vides à la fin. Un exemple est donné en bas de l’encadré.
Cette patience est déterministe : une fois le paquet de cartes mélangé, il conduit à perdre ou gagner sans que cela dépende de la stratégie adoptée. En revanche, la question de la probabilité de gagner est un intéressant sujet de réflexion pour l’amateur mathématicien.
Voyons la solution complète de « Tout débarrasser ». Notons 0 pour une carte rouge et 1 pour une noire. Soient k et h deux entiers positifs. Considérons une suite S formée de 2k 0 et 2h 1. Nous dirons qu’elle est « débarrassable » si l’on gagne la réussite avec cette suite.
Propriété 1. S est débarrassable si on peut la vider en enlevant, sans aucun ordre particulier, des paires de 0 consécutifs et des paires de 1 consécutifs, comme dans l’exemple : 01001110 → 011110 → 0110 → 00 → Vide.
Démonstration. Si on peut vider la suite dans un certain ordre, on peut la vider en s’imposant de supprimer la paire la plus à gauche quand on a des choix, ce qui correspond à l’application des règles de la réussite « Tout débarrasser ». En effet, une paire qu’on peut enlever reste toujours enlevable si on en enlève d’autres avant.
Propriété 2. S est débarrassable si et seulement si la propriété (E) suivante est vérifiée : « La moitié des 0 occupent des places de numéro pair et l’autre moitié des 0 occupent des places de numéro impair. »
Notons que la propriété (E) avec 0 implique la propriété (E) avec 1 et réciproquement.
Exemple d’une suite vérifiant (E) : 0 1 0 0 1 1 1 0. Il y a en effet deux 0 en position paire (les positions 0 et 2, en rouge) et deux 0 en position impaire (les positions 3 et 7, en bleu).
Démonstration.
a) Si S est débarrassable, alors S vérifie (E). Lorsqu’on enlève une paire de 0 (respectivement de 1), on enlève toujours un 0 (resp. un 1) en position paire et un 0 (resp. un 1) en position impaire, puisque les positions occupées sont consécutives. Quand on resserre la suite pour boucher un trou qu’on vient de faire en enlevant une paire, on ne change pas la parité des éléments de la suite : ceux en position paire le restent, et de même pour ceux en position impaire. Il en résulte qu’à chaque étape on enlève un 0 (resp. un 1) en position paire et un 0 (resp. un 1) en position impaire. Au total donc, si on peut vider la suite, c’est qu’elle vérifie la propriété (E) pour les 0 et pour les 1.
b) Si S vérifie (E), alors S est débarrassable. Si S vérifie (E) alors elle contient au moins une paire de 0 consécutifs, ou une paire de 1 consécutifs. En effet : si S ne contient ni paire de 0 consécutifs, ni paire de 1 consécutifs, c’est que les 0 et les 1 alternent, et donc que les positions des 0 ont toutes la même parité et donc que (E) n’est pas vérifiée. On remarque ensuite que si une suite vérifie (E) et qu’on lui enlève une paire de 0 consécutifs, ou une paire de 1 consécutifs, alors la nouvelle suite après avoir resserré ses éléments vérifie encore la propriété (E). Il en résulte de proche en proche que si S vérifie (E), alors S est débarrassable.
Propriété 3.
a) Il y a C(2k + 2h, 2k) suites possibles de 2k 0 et 2h 1, où les C(p, q) = p !/[(p – q) ! q !] sont les coefficients du binôme de Newton.
b) Parmi ces suites, il y en a [C(k + h, k)]2 qui sont débarrassables.
Démonstration.
a) Déterminer une suite S formée de 2k 0 et 2h 1, c’est choisir 2k emplacements pour les 0, ce qui revient à choisir 2k éléments dans un ensemble de 2k + 2h éléments. Or C(p, q) est le nombre de façons de choisir q éléments dans un ensemble de p éléments, d’où le résultat.
b) Choisir une suite qui vérifie (E), c’est : 1) choisir les k places paires où l’on met les 0, soit C(k + h, k) choix possibles ; 2) choisir les k places impaires où l'on met des 1, soit également C(k + h, k) choix possibles. Les deux choix sont indépendants, d’où le résultat.
En pratiquant la réussite, on comprend et on démontre que la réussite « Tout débarrasser » est équivalente à la suivante, plus simple mais qui exige une surface plus grande pour poser les cartes : (a) étaler en ligne les L cartes sur la table de gauche à droite ; (b) tant que c’est possible, enlever une paire de cartes de la même couleur côte à côte et rapprocher les cartes qui restent alors sur la ligne (cela sans s’occuper de l’ordre des retraits). On gagne s’il ne reste plus rien.
Cette remarque mène à la conclusion pas tout à fait évidente qu’un paquet de cartes conduit à gagner si et seulement si le même paquet utilisé à l’envers permet de gagner. On démontre aussi que si un paquet de cartes P permet de gagner, tous les paquets de cartes obtenus en coupant P (on sépare n’importe où le paquet en deux et on échange la partie en dessous avec celle au-dessus) permettent aussi de gagner (voir la propriété (E) de l’encadré 3).
La réussite peut s’envisager avec n’importe quel jeu de cartes, pourvu qu’il comporte un nombre pair de cartes rouges et un nombre pair de cartes noires. On envisagera par exemple la réussite « Tout débarrasser » avec 2 cartes noires et 2 cartes rouges que nous noterons TD-2, ou avec 4 cartes noires et 4 cartes rouges que nous noterons TD-4, etc. La réussite étant déterministe, aucune stratégie n’est à rechercher ; en revanche, le calcul de la probabilité de gagner est un défi. Un premier calcul consiste à engendrer toutes les configurations possibles, à les jouer et à compter combien de fois on gagne. L’ordinateur bien évidemment fait le travail !
Les énumérations deviennent trop longues pour aller plus loin, du moins avec mon programme et mon ordinateur. En utilisant l’encyclopédie en ligne des suites numériques de Neil Sloane (https://oeis.org) et en l’interrogeant sur la suite (4, 36, 400, 4 900) calculée par l’ordinateur, le site internet indique qu’il pourrait s’agir de la suite [C(2n, n)]2, où les C(p, q) = p !/[(p – q) !q !] désignent les coefficients du binôme de Newton. Le nombre suivant donné par l’encyclopédie est 63 504 ; il correspond à celui que nous avons calculé. Il est difficile d’imaginer que c’est par hasard.
Pour tester cette formule, nous avons donc procédé à une seconde évaluation en procédant par simulation répétée. En opérant 100 000 tirages au sort de configurations initiales pour chaque longueur de paquet de cartes, nous avons évalué la probabilité de gagner pour TD-12, TD-14, …,TD-26, que l'on a comparée au nombre donné par la suite de l’encyclopédie de Neil Sloane divisé par le nombre de configurations initiales possibles, qui est C(4n, 2n) pour TD-2n.
Le tableau de probabilités obtenu expérimentalement correspond assez bien au tableau de probabilités provenant de la formule de l’encyclopédie de Sloane.
Partant de cette information, nous avons recherché une caractérisation des configurations gagnantes permettant d’arriver à la formule [C(2n, n)]2. Nous avons pu la trouver et établir que le nombre de configurations gagnantes dans le cas de 2k cartes rouges et 2h cartes noires est [C(k + h, h)]2, et par conséquent que la probabilité de gagner est [C(k + h, h)]2/C(2k + 2h, 2h) (voir l’encadré 3).
La patience « Tout débarrasser » est donc entièrement traitée et, grâce à la formule, vous pouvez savoir en fonction du paquet que vous utiliserez quelle est votre probabilité de gagner : avec un paquet de 32 cartes, vous gagnerez dans 27,55 % des cas ; avec un paquet de 52 cartes, ce ne sera que 21,81 %. On notera que dans cette étude, l’utilisation de l’encyclopédie des suites numériques a été déterminante. Il est probable que, sans l’utiliser, jamais je n’aurais pu établir le résultat général.
Considérons maintenant une réussite en rouge en noir qui m’a été expliquée à Hermione (Ermioni), en Grèce. Elle semble intéressante car, bien que déterministe et très simple, il est difficile d’en comprendre toutes les propriétés et en particulier de calculer la probabilité de gagner autrement que par simulation informatique et évaluation statistique.
Cette patience n’exige pas de table, on pourra donc la pratiquer dans un bus ou en voiture. On tient le jeu battu dans la main gauche et on fait passer les cartes deux par deux dans la main droite.
On met les deux cartes au-dessus si elles sont de la même couleur, sinon on les met sous le paquet en les laissant dans le même ordre. Petit à petit, le paquet passe de la main gauche à la main droite. Le nombre de paires de même couleur sur le dessus du paquet est la valeur du paquet. Ce nombre est forcément pair. En effet, les cartes qui composent ces paires contiennent autant de rouges que de noires puisque c’est le cas du reste du paquet, ce qui oblige à un nombre pair de paires de la même couleur au-dessus du paquet. Avec un jeu de 32 cartes, ce nombre peut donc être 0, 2, 4, 6, 8, 10, 12, 14 ou 16.
Quand on a terminé une manipulation, on ne mélange pas le jeu, on prend la carte du dessus du paquet et on la place en dessous. On fait alors passer le paquet de la main droite à la main gauche, et on recommence la manipulation.
À la fin de chaque manipulation, on note la valeur du paquet obtenu. On trouve par exemple la suite de valeurs 6, 2, 6, 4, 8, 8, etc. On a gagné si l'on réussit à avoir une valeur supérieure à 8 (donc 10, 12, 14, 16).
On est tenté d’essayer longtemps, mais souvent on échoue, aucune valeur supérieure à 8 ne se produisant. On constate qu’on tombe aussi sur ce qui semble être un cycle de valeurs, par exemple 8, 6, 8, 6, … Obtenir 14 semble difficile, et 16 encore plus ! Pourtant, c’est évidemment possible. Une simulation informatique avec 100 000 tentatives donne : 0 fois 0, 0 fois le 2, 133 fois le 4, 4 670 fois le 6, 36 830 fois le 8, 44 100 fois le 10, 13 081 fois le 12, 1 185 fois le 14, 1 fois le 16.
On a donc environ 58,3 % de chances d’obtenir un paquet ayant une valeur 10 ou plus, 14,3 % d’avoir 12 ou plus, 1,2 % d’avoir 14 ou plus.
Quelques questions se posent. Quelle est la longueur du plus long cycle de résultats pour un jeu de 32 cartes ? Quelle est la plus longue attente avant d’entrer dans un cycle pour un jeu de 32 cartes ? Que se passe-t-il plus généralement pour des jeux de K cartes rouges et K cartes noires ? Pour la première question, on a une idée. Une série de nombreux essais semble montrer que quel que soit le paquet de K cartes rouges et K cartes noires, la manipulation finit inévitablement par tomber sur une suite constante de valeurs (par exemple 8, 8, 8…) ou sur un cycle d’ordre deux (par exemple 12, 10, 12, 10). Qui saura le démontrer ?
Il existe des dizaines de travaux mathématiques consacrés aux patiences et solitaires et il s'en publie encore régulièrement. Les patiences prenant en compte seulement les couleurs rouge et noire devraient être les plus simples, mais, finalement, ce n’est pas si sûr. Elles semblent une riche source de problèmes de tous niveaux. Le fait de ne manipuler que deux valeurs possibles pour les cartes intéressera les informaticiens, dont on sait qu’ils adorent le binaire ; mais, plus généralement, elles pourraient occuper mathématiciens et amateurs de programmation pour les longues journées de vacances pluvieuses ou… d’épidémie.
Jean-Paul Delahaye est professeur émérite à l’Université de Lille et chercheur au centre de recherche en informatique, signal et automatique de Lille (CRISTAL). Il est l’auteur de la rubrique Logique et calcul dans Pour la Science et du blog Complexités.
Voir tous ses articlesI. Gent et C. Blake, Patience experimental results, 2019.
C. Blake et I. P. Gent, The winnability of Klondike solitaire and many other patience games, prépublication, 2019.
A. Tung, A brief history of Solitaire, Patience, and other card games for one, The Week, 2015.
C. Jefferson et al., Modelling and solving English Peg Solitaire, Computers & Operations Research, vol. 33(10), pp. 2935-2959, 2006.
X. Yan et al., Solitaire : Man versus machine, Advances in Neural Information Processing Systems, vol. 17, pp. 1553-1560, 2005.
E. Berlekamp et al., Purging pegs properly, Winning Ways for Your Mathematical Plays (2e éd.), vol. 4, pp. 803-841, A K Peters, 2004.
S. de Mora-Charles, Quelques jeux de hasard selon Leibniz, Historia Mathematica, vol. 19, pp. 125-157, 1992.
Identifiables au premier coup d’œil, ces structures étonnantes et magnifiques défient pourtant les mathématiciens, qui peinent à en donner la définition.
Comment représenter toutes les permutations possibles d’un ensemble par une courte séquence ? Ce jeu de tassement n’intéresse pas seulement les mathématiciens : il peut aussi aider les étourdis, les cambrioleurs et les voyageurs de commerce.
La combinatoire géométrique exige une patience et une minutie dont souvent seul l’ordinateur est capable. Le cas des tétrades est exemplaire.
Des champs de neige rouge dans les montagnes, des averses pourpres, des traces sanglantes de pas sur un tapis neigeux immaculé… Au
Laisser des trous dans un assemblage de carrés en minimisant le nombre de pièces utilisées : ce problème de géométrie n’est pas facile. Mais le cheminement vers sa solution illustre bien la démarche des mathématiciens.
Disposer des formes géométriques identiques dans le plus petit espace possible : les problèmes de ce type attirent non seulement les amateurs de récréations mathématiques, mais aussi des chercheurs de métier.
