Jack et le haricot magique: le jeu ! (Première partie)

Non, il ne s’agit pas ici d’une pub pour un jeu exploitant honteusement une licence payée à prix d’or. Il s’agit tout simplement d’un jeu mathématique inventé par John Isbell et qui a pour habillage le célèbre conte Jack et le haricot magique. Pour ceux qui ne connaitraient pas ce conte, voici un résumé ci-dessous.

Le conte, version 2011

Attention ! Ce conte contient des scènes pouvant heurter la sensibilité des plus jeunes. Veuillez les tenir éloignez de ce blog durant la lecture de ce paragraphe.

Jack est un jeune délinquant fumeur de shit aux cheveux sales qui se voit contraint par sa mère d’aller vendre son plus jeune frère au marché parce que ce dernier coûte dorénavant plus cher à nourrir que les quelques euros qu’il rapporte en allocations familiales. En pleine crise de manque, Jack oublie sciemment les consignes de sa génitrice et décide d’utiliser les quelques billets qu’il vient d’obtenir de la part du sosie de Frédéric Mittérand en échange de son frère (mineur) pour acheter un peu d’herbe destinée à sa consommation personnelle. Cependant, il ne trouve pas son dealer habituel et se rabat donc sur un revendeur du troisième âge qu’il ne connaît pas (et qui, faute de n’avoir pu cotiser pendant 42 ans, se retrouve obligé de vendre des substances illicites dans la rue afin de pouvoir suivre le même train de vie qu’il aurait s’il avait une retraite à taux plein). Jack a beau n’avoir manqué aucune émission de Julien Courbet depuis 13 ans, il n’échappe malgré tout pas à l’arnaque: les boulettes de cannabis qu’il pense acheter se trouvent en fait être de banals haricots. Tout juste de retour devant sa maison, Jack croise une patrouille de Police et s’empresse alors de jeter le paquet de haricots dans le jardin avant de se réfugier dans sa chambre pour y trouver le sommeil.

Sans doute encore sous l’effet du LSD consommé la veille, le jeune Jack se réveille en voyant un énorme tronc d’arbre grimpant jusqu’au ciel dans son jardin. Tout toxicomane qu’il est, il ne réfléchit pas à deux fois avant de se décider à grimper à l’arbre, espérant peut-être trouver là-haut quelques graines de pavot qu’il se voit déjà faire pousser à profit en suivant les précieux conseils qu’il a reçus de la fine fleur des agriculteurs Afghans lors de sa récente tournée en Asie.

Arrivé à la cime de l’arbre, Jack tombe sur une immense maison-close où il se fait racoler agressivement par une péripatéticienne dont l’état de délabrement physique aurait dû lui interdire d’exercer sa profession. N’ayant pas connu l’amour charnel depuis quelques mois, quelques mycoses vaginales et de l’herpès génital n’ont pas freiné les ardeurs de Jack lorsque la maîtresse de maison lui a proposé un massage thaïlandais. Après avoir fait sa petite affaire tout en refusant de payer un prix de toute façon trop cher vu la marchandise, Jack se rend compte que le proxénète de cet établissement n’est autre qu’un ogre qui a pour curieuse habitude de dévorer tout client qui n’est pas un habitué des lieux (à la rigueur, pourquoi pas, d’autres sont bien des barbiers qui ne rasent que ceux qui ne se rasent pas eux-mêmes et ça ne choque personne). C’est alors que Jack a la bonne idée de se cacher dans une des miteuses chambres de passe, échappant ainsi de peu à un règlement de comptes digne du Milieu Marseillais. Il en profite même pour voler dans la caisse, ce qui lui permet d’apporter à sa brave maman de l’argent aussi propre que Bernard Tapie dans l’affaire VA-OM.

C’est le début d’une période faste pour Jack, une période où l’argent facile le mène à une vie de débauche, où les filles faciles, la cocaïne et le champagne coulent à flots tous les soirs. Mais vient le jour où, lors d’un énième vol de caisse dans la maison de l’ogre, Jack se fait prendre la main dans le sac tel un DSK dans une chambre au 28ème étage d’un hôtel New-Yorkais. Le proxénète comptant bien récupérer l’argent que le jeune homme n’a pas daigné donner en échange des faveurs de cette dame à la vertu aussi fine que son hymen, il se met à poursuivre le jeune brigand qui arrive à parvenir jusqu’au tronc d’arbre sur lequel il se laisse glisser pour rejoindre la terre ferme. Arrivé au sol avant le géant (dont le postérieur beaucoup trop imposant l’empêche d’aller aussi vite qu’il ne le souhaite), il demande à sa mère la tronçonneuse qu’il avait commandée lors d’une matinée d’ennui passée devant le Téléachat afin de couper l’arbre, qui finira par tomber, emmenant dans sa chute l’ogre.

A ce point, l’histoire devient un peu moins claire et les différents rapports de Police sur l’affaire ne concordent pas tous.  Cependant, on est en mesure d’affirmer qu’aucunes traces d’un ogre ou d’un quelconque arbre géant n’ont été retrouvées. Ni l’existence du dealer vieillard, ni celle de la prostituée n’ont été prouvées. Il semblerait qu’il s’agisse là d’un simple délire hallucinatoire provoqué, selon toute vraisemblance, par une surconsommation de diacétylmorphine. Jack n’aurait pas bougé de son lit depuis le début de l’histoire jusqu’au moment où, ne donnant plus aucun signe de vie, sa mère aurait décidé de l’emmener aux urgences, le sauvant ainsi d’une overdose certaine.

La morale de ce conte est: « Dites non à la drogue ». A moins que la morale soit plutôt: « Dites non aux haricots ». Bref, revenons aux maths…

Règles du jeu

Dans un (rare) moment de lucidité où il n’est sous l’influence d’aucune substance suspecte, Jack propose à l’ogre de jouer au petit jeu suivant:

  1. L’ogre commence la partie en choisissant un nombre entier positif n_0 plus grand que 1.
  2. A chaque étape i, si le nombre n_i choisi est pair, le joueur suivant doit choisir le nombre n_{i+1}:= \frac{n_i}{2}.
  3. Et si le nombre n_i choisi est impair, le joueur suivant peut choisir soit le nombre n_{i+1}:= 3n+1, soit le nombre n_{i+1}:= 3n-1.
  4. Le premier joueur arrivant à 1 est gagnant.

Un petit exemple vaut plus qu’une longue explication:

  • L’ogre choisit le nombre 6.
  • Jack doit choisir le nombre 6/2 = 3 car le nombre précédent est pair.
  • Le nombre choisi par Jack étant impair, l’ogre peut choisir soit 3×3+1=10 ou bien 3×3-1=8. Il choisit 10.
  • Jack doit choisir 5.
  • L’ogre peut choisir 3×5+1=16 ou 3×5-1=14. Il choisit 16.
  • Jack doit choisir 8.
  • L’ogre doit choisir 4.
  • Jack doit choisir 2.
  • L’ogre doit choisir 1 et gagne.

Afin de pimenter un peu le jeu, les deux joueurs donnent un enjeu à chaque partie: si l’ogre gagne, il peut dévorer Jack. Et si Jack gagne, il repart sain et sauf avec l’or du géant. Le but pour Jack est donc de trouver une stratégie qui lui permette de gagner à coup sûr, ou du moins ne pas perdre (car a priori rien n’empêche qu’il puisse exister des parties qui n’atteignent jamais 1, auquel cas on déclare l’égalité entre les deux joueurs).

Puisque c’est Jack qui propose ce jeu à l’ogre, il doit donc décider d’une (ou plusieurs) règles à ajouter au jeu afin qu’il sorte toujours vainqueur ou bien à égalité avec son adversaire.

Pourquoi avoir choisi Jack et le haricot magique comme contexte pour ce jeu ?

Imaginons qu’on gradue de bas en haut et tous les mètres l’arbre géant créé par les haricots magiques. Ce jeu symbolise la course poursuite sur l’arbre entre Jack et l’ogre: si l’ogre est initialement à la graduation n_0, alors Jack se déplace ensuite à la hauteur n_1, puis l’ogre à la hauteur n_2… La premier arrivé à la hauteur 1 (donc au pied de l’arbre en quelques sortes) peut couper l’arbre et faire tomber l’autre. Bon, je suis d’accord, il n’y a qu’un mathématicien pour faire un lien entre ce conte et ce petit jeu… mais je trouve l’analogie plutôt parlante au final !

Quelques cas simples

Jack n’étant pas idiot, il a bien compris que si l’ogre choisit le nombre 1 au départ, il perd immédiatement la partie. Jack ajoute donc dans la règle du jeu l’interdiction de choisir n_0=1 au départ.

D’autre part, Jack comprend que si les nombres sont pairs à chaque étape, il n’aura aucun choix à aucun moment de la partie puisque les nombres qu’il devra choisir seront la moitié des nombres choisis par l’ogre. Cette situation se produit si le nombre choisi par l’ogre au départ est de la forme n_0=2^q. Supposons donc que tel soit le cas:

  • Au départ, l’ogre choisit n_0=2^q.
  • A la première étape, Jack doit choisir n_1=2^{q-1} qui est pair.
  • A la deuxième étape, l’ogre doit donc choisir n_2=2^{q-2}.
  • etc.

La partie se termine donc à l’étape i telle que n_i=2^{q-i}=1 c’est-à-dire lorsque i=q. Puisque l’ogre joue à toutes les étapes d’indice pair, il gagnera si q est pair, et Jack gagnera si q est impair. Vous pouvez tester par vous-mêmes, si l’ogre choisit 16 ou 64 au départ, il est gagnant, s’il choisit 8 ou 32, il est perdant.

Jack ne pouvant pas laisser la moindre possibilité au géant de gagner, il se doit donc d’interdire le choix au départ de toute puissance de 2. Au passage, on peut en déduire une stratégie en cours de partie: si à un moment du jeu on peut choisir un nombre qui est une puissance paire de 2, alors on est gagnant à coup sûr (et a contrario, si à un moment on choisit un nombre qui est une puissance impaire de 2, on est perdant).

Jack poursuit sa réflexion et envisage le cas où le géant choisit au départ un nombre pair (qui n’est pas une puissance de 2). Nous avons déjà vu l’exemple plus haut de n_0=6 dans lequel le géant est sorti vainqueur et dans lequel Jack n’a eu le choix à aucun moment. Remarquons qu’à un moment l’ogre avait le choix entre 10 et 8. S’il avait choisi 8, il aurait perdu comme on l’a expliqué précédemment. Là encore, pour ne pas risquer de perdre, Jack est dans l’obligation d’interdire que le nombre de départ choisi soit pair.

Le théorème des haricots magiques et la stratégie de la cachette

Jack doit donc envisager le cas où le nombre de départ est impair (en espérant qu’il existe dans ce cas une stratégie favorable pour lui s’il ne veut pas finir dans l’assiette de l’ogre !).

Commençons par un exemple:

  • L’ogre choisit 7.
  • Jack a le choix entre 20 et 22. Il choisit 22.
  • L’ogre est forcé de choisir 11.
  • Jack doit décider entre 32 et 34. Il se souvient de l’histoire des puissances de 2 et évite soigneusement 32 et prend 34 à la place.
  • L’ogre choisit 17.
  • Jack doit choisir entre 50 et 52. Il choisit 50.
  • Ogre: 25.
  • Jack a le choix entre 74 et 76. Il prend 74.
  • Ogre: 37.
  • Etc.

Il semble que les nombres augmentent de plus en plus, et, à première vue, on a peu de chances d’atteindre 1. De plus, on remarque qu’à chaque fois que Jack a eu le choix, c’était entre deux nombres pairs, dont l’un est un nombre dont la moitié est un nombre pair, et l’autre est un nombre dont la moitié est un nombre impair. Pour avoir toujours le choix, Jack a pris à chaque fois le nombre dont la moitié est un nombre impair. Ainsi, l’ogre, qui n’a de toutes façons pas le choix, propose un nombre impair, ce qui laisse ensuite encore le choix à Jack. Nous voyons donc un début de stratégie qui permet à Jack, si ce n’est de gagner, d’au moins faire durer le jeu suffisamment longtemps pour qu’on puisse déclarer une égalité.

Nous allons prouver la stratégie adoptée dans cette exemple dans un contexte plus général: c’est ce qu’on appellera le théorème des haricots magiques et il s’énonce de la façon suivante

Si n_0 est impair (différent de 1), alors Jack n’est jamais obligé de perdre.

Autrement dit, dans le cas d’un nombre de départ impair, Jack possède une stratégie pour ne jamais perdre, mais cela ne signifie pas pour autant qu’il peut gagner.

Prouvons le théorème par récurrence. En fait, nous allons montrer qu’à chaque étape, si le nombre de l’ogre était impair, Jack peut par son choix obliger l’ogre à choisir des nombres encore impairs et de plus en plus grands (ce qui empêche donc l’ogre d’atteindre 1 un jour ou l’autre).

Un nombre impair est toujours de la forme 4m+1 ou bien 4m-1. Supposons qu’à l’étape i (forcément paire mais c’est sans importance), l’ogre ait choisi le nombre impair n_i=4m+1 (respectivement n_i=4m-1 ). Dans ce cas, Jack a le choix entre les nombres n_{i+1}=3(4m+1)+1=12m+4 ou n_{i+1}=3(4m+1)-1=12m+2 (respectivement n_{i+1}=3(4m-1)+1=12m-2 ou n_{i+1}=3(4m-1)-1=12m-4). Dans tous les cas, Jack peut choisir soit un nombre de la forme 12m+2 (pair), ou bien un nombre de la forme 12m-2 (pair aussi), ce qui, à l’étape i+2, impose à l’ogre le nombre impair de la forme n_{i+2}=6m \pm 1 qui est plus grand que le nombre 4m \pm 1 qu’il avait choisi à l’étape i.

Cette stratégie s’appelle la stratégie de la cachette, car Jack, même s’il ne perd jamais, reste malgré tout sur l’arbre sans en descendre. Pire, il montera toujours plus haut mais au moins, l’ogre n’atteindra jamais 1.

Et si Jack veut absolument gagner pour repartir avec l’or tout en étant sûr de ne jamais laisser l’ogre le dévorer ? Nous étudierons cela dans la deuxième partie de cet article… (ça c’est du teaser !)

Advertisements
Cet article, publié dans Arithmétique, Nombres, est tagué . Ajoutez ce permalien à vos favoris.

3 commentaires pour Jack et le haricot magique: le jeu ! (Première partie)

  1. Glamourowls dit :

    « Veuillez les tenir éloignez » –> une faute d’orthographe s’est glissée quelque part. 🙂
    Sinon belle réécriture du conte. Très 21e siècle ! xD
    Daly

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s