La magie des colliers de perles de Nicolaas Govert de Bruijn

Piste bleue 25 septembre 2014  - Rédigé par  Michel Rigo Voir les commentaires (4)

Préparer un tour de magie ou construire des colliers de perles particuliers revient en fait à trouver un circuit particulier dans un graphe ayant de nombreuses propriétés mathématiques.

Nous vous présentons ici un tour digne d’un magicien professionnel. Dans une salle de spectacle, ou pour une prestation en « close-up », le prestidigitateur présente brièvement aux spectateurs attentifs un jeu de trente-deux cartes. Il s’agit d’un jeu de belote tout à fait classique. Les cartes du paquet paraissent être disposées de façon aléatoire comme sur l’image ci-dessous (nous utiliserons cette disposition tout au long de l’article).

« Vous conviendrez aisément que ce jeu n’a pas été classé de façon particulière » lance le magicien. Ensuite, celui-ci propose à un spectateur désigné au hasard (n’ayez crainte, il ne s’agit nullement d’un comparse) de couper le jeu.

Ensuite, ce spectateur prend la carte en haut du paquet (sans la montrer au magicien) et distribue à ses voisins les cinq cartes au sommet du tas. Le magicien ne voit pas les cartes distribuées. A la demande du magicien, ces cinq personnes énoncent, à haute voix, la couleur de leur carte (simplement s’il s’agit d’une carte rouge ou noire). On a pris soin de ne pas rendre le jeu au magicien et celui-ci ne dispose d’aucune autre information que la couleur des cinq cartes. Il ne trichera pas plus que nécessaire...

Cependant, après s’être concentré, le maître énonce une à une les six cartes que les spectateurs cachent en main (y compris la carte du premier spectateur, dont le magicien ne connaissait a priori rien, même pas la couleur). Les six spectateurs étonnés montrent leur carte à l’ensemble du public qui applaudit alors chaudement.

Ce tour, plutôt époustouflant, vous en conviendrez [1], repose sur une propriété combinatoire : l’astuce est de ranger les cartes du paquet de façon spécifique. En effet, le magicien avait, au préalable, classé les cartes du jeu. Il y a toujours un truc ! Nous allons vous expliquer sur quoi ce tour est basé et comment le réaliser.

Première explication

Considérons une version simplifiée du tour avec un jeu à huit cartes. Le spectateur désigné coupe le jeu, garde une carte et distribue les trois suivantes à ses voisins.

Commençons par une digression. Nous allons tout d’abord fabriquer un collier constitué de huit perles : 4 noires et 4 rouges. On peut, par exemple, obtenir le collier ci-dessous.

Ce collier possède une propriété remarquable et primordiale pour notre tour de magie : si l’on démarre avec deux perles en des positions différentes (par exemple, celles numérotées 1 et 5 sur la figure) et que l’on regarde, dans l’ordre, les couleurs de 3 perles consécutives en avançant dans le sens des aiguilles d’une montre, alors on ne verra jamais deux fois la même suite de 3 perles. Ainsi, depuis la perle 1, c’est-à-dire en regardant les perles 1, 2 et 3, on voit la suite noir-rouge-noir. Par contre, depuis la perle 5, en regardant les perles 5, 6 et 7, on voit la suite noir-rouge-rouge.

Si on y regarde même d’un peu plus près, on verra que chaque suite possible de 3 perles de couleur apparaît une et une seule fois. Ainsi, la figure ci-dessous reprend toutes les configurations possibles pour 3 perles (3 rouges, 2 rouges/ 1 noire, 2 noires/ 1 rouge, 3 noires). Le nombre placé en dessous indique la position de la perle à partir de laquelle on retrouve cette configuration. Notez qu’avec 8 perles pouvant servir de perle de départ, on n’aura jamais plus de 8 configurations possibles.

C’est cette propriété qui est utile au magicien. Si on lui fournit une suite de 3 perles de couleur, il sait précisément quelle perle du collier est prise comme point de départ. Par exemple, si on lance « noir-noir-rouge », alors c’est que la perle de départ porte le numéro 4. Remarquons aussi que connaître la couleur de deux perles consécutives ne suffit pas : depuis les perles 1 et 5, on voit la même suite noir-rouge.

Fournir une suite de 3 couleurs de perle permet de se positionner de façon unique au sein du collier.

Revenons maintenant au tour de cartes et faisons le lien avec notre collier de perles. Prenons 8 cartes : Valet, Dame, Roi, As de coeur et de pique. On a donc 4 cartes rouges et 4 cartes noires. Le magicien décide d’arranger les 8 cartes comme suit : As de pique, Valet de coeur, Valet de pique, Roi de pique, Dame de pique, As de coeur, Roi de coeur et Dame de coeur. En effet, cet arrangement, si on se limite aux couleurs rencontrées, correspond exactement au collier de 8 perles que nous avons présenté plus haut.

Le magicien pourrait considérer un autre arrangement tant que ce dernier respecte l’ordre des couleurs mais il faut bien en fixer un. Imaginons maintenant que le spectateur désigné ait coupé [2] le jeu de telle façon que la carte du dessus soit le Valet de pique. En effet, le fait que l’on autorise de couper le jeu revient à voir les cartes comme arrangées dans un collier. Après la coupe, la carte qui se trouvait en bas du paquet est maintenant suivie par celle qui occupait le sommet du tas avant la coupe. Si le spectateur désigné a le Valet de pique, les voisins reçoivent respectivement le Roi de pique, la Dame de pique et l’As de coeur. Ces 3 spectateurs affirment avoir, dans l’ordre, la suite de couleurs noir-noir-rouge. Ainsi, le magicien qui sait comment les cartes étaient rangées initialement, dispose de toute l’information nécessaire et retrouve les 4 cartes cachées. La suite noir-noir-rouge correspond aux cartes : Roi de pique, Dame de pique, As de coeur. La carte précédente, conservée par le spectateur désigné, est donc bien le Valet de pique.

On peut appliquer ce principe à un collier (et donc à un jeu de cartes) plus grand et rendre ainsi le tour plus impressionnant. Voici à présent un collier formé de 16 perles rouges et 16 perles noires.

Ici, le collier est construit de telle sorte que chacune des 32 suites de 5 perles de couleur rouge/noire y apparaisse une et une seule fois (on l’affirme ici, le détail menant à la construction d’un tel collier est donné plus bas). On retrouve la propriété du collier de 8 perles mais étendue à un collier plus grand.

Pour le collier de 32 perles ci-dessus, fournir une suite de 5 couleurs de perle permet de se positionner de façon unique au sein du collier.

Comme précédemment, on peut encore observer que connaître la couleur de quatre perles consécutives ne suffit pas : par exemple, la même suite noir-noir-rouge-rouge apparaît deux fois dans le collier.

Reprenons maintenant le jeu de belote de 32 cartes montré initialement. Il correspond exactement au collier représenté ici. En effet, si vous passez en revue les perles du collier en commençant par celle placée à midi (et en suivant le sens des aiguilles d’une montre, ou, dans le sens « horlogique » comme on le dirait en Belgique), vous retrouvez exactement la suite des couleurs du jeu de belote de notre magicien.

Ainsi, le magicien professionnel ayant étudié la suite de 32 cartes, non seulement leurs couleurs mais aussi leurs valeurs, n’aura aucun problème à retrouver les cartes des spectateurs. On peut aussi supposer que le magicien dispose d’une anti-sèche [3] ou d’un moyen mémo-technique pour retenir facilement la suite de cartes.

Quelques exemples (vous pouvez vous aider de l’image reprise ci-dessous), si les 5 voisins fournissent une suite de 5 couleurs :

  • rouge-rouge-noir-noir-rouge, la première carte correspondant à cette série de 5 couleurs est la dame de carreau (et la carte précédente, c’est-à-dire celle prise par le premier spectateur, est le 10 de trèfle) ;
  • noir-noir-noir-rouge-noir, la première carte de la série est le roi de pique (et celle qui précède est l’as de pique) ;
  • rouge-rouge-rouge-noir-rouge, la première carte de la série est le 8 de carreau (et celle qui précède est la dame de trèfle).
  • Un dernier exemple plus compliqué : rouge-noir-rouge-rouge-rouge... la première carte de la série est l’as de carreau (et celle qui précède est le roi de coeur). Il ne faut pas oublier que l’on a coupé le jeu donc si le « collier » se referme, le 7 de pique est suivi de la dame de coeur ;
  • et ainsi de suite...

Pourquoi avoir pris 8, 16, 32 perles/cartes ? Il faut savoir que le nombre de suites possibles de 3 perles rouges ou noires est exactement $2\times 2\times 2$ car la première perle peut prendre deux couleurs et il en est de même pour les perles suivantes. Ainsi, pour chaque perle prise en compte, on double successivement le nombre de possibilités de suites. Tous les cas possibles sont repris dans la figure ci-contre. A gauche, on choisit d’abord la couleur de la première perle. Une fois ce choix effectué, on sélectionne la couleur de la deuxième perle, etc.

Ainsi, avec un collier de 8 perles, on peut espérer retrouver les 8 suites possibles de trois perles de couleur. Le lecteur pourra se convaincre qu’il y a exactement 16 suites de 4 perles et 32 suites de 5 perles (toujours de couleur rouge ou noire). En effet, $32=2\times 2\times 2\times 2\times 2$.

Est-ce que tous les colliers formés de 8 perles (4 noires et 4 rouges) ont cette propriété magique ? Certainement pas, observez le collier repris ci-dessous. On y voit deux fois la suite rouge-rouge-rouge (si on démarre de la position 6 ou 7). Mais on ne voit jamais la suite rouge-noir-rouge.

Rencontrer deux fois la même suite rend la tâche impossible au magicien, il ne peut pas déterminer à coup sûr l’endroit où le spectateur a coupé le jeu... La situation est encore pire avec le collier suivant.

Ici, les suites noir-rouge-noir et rouge-noir-rouge apparaissent 4 fois chacune ! Par conséquent, le magicien peut uniquement déterminer si la position de la première perle est paire ou impaire.

La construction

Comme on vient de le voir, si on place « au hasard » 4 perles rouges et 4 perles noires, on risque fort comme dans les deux derniers colliers représentés ci-dessus de ne pas voir apparaître chaque suite de 3 perles de couleur une et une seule fois. Une même suite apparaîtra dès lors plus d’une fois et le magicien ne sera pas en mesure de retrouver systématiquement la position initiale. Imaginez maintenant avoir 16 perles rouges et 16 perles noires. Comment réussir à construire à coup sûr un collier ayant la propriété recherchée, i.e., chaque suite de 5 perles de couleur y apparaît une et une seule fois ? Il y a de fortes chances en tâtonnant par essai-erreur d’y passer un temps très long, voire même, si on s’y prend mal, de ne jamais y arriver. Pourtant, on sait qu’un tel collier peut être construit, nous l’avons déjà représenté plus haut. [4]

Dans cette troisième partie, la plus intéressante mathématiquement, nous allons donner un moyen de construction systématique pour trouver de tels colliers (et donc être en mesure de réaliser le tour de magie). Il faut construire ce que l’on appelle un graphe de de Bruijn. Un graphe est un « dessin » constitué de sommets et de « flèches » reliant ces sommets. Rassurez-vous, la construction est assez simple. Pour ne pas avoir un dessin trop grand, nous allons nous limiter, une fois encore, au cas des 8 cartes. Les « sommets » du graphe sont les 8 configurations possibles de 3 couleurs. Les voici représentées à nouveau :

Maintenant, il faut expliquer comment tracer des « flèches » entre ces sommets. Il y a deux types de flèches, des rouges et des noires et une flèche de chaque type part de chaque sommet. La règle permettant de déterminer le sommet atteint est assez simple : partant d’une configuration donnée de trois perles, pour déterminer la configuration à atteindre, il faut supprimer la première perle et ajouter à droite des deux perles restantes une perle ayant la même couleur que la flèche. Un exemple est explicité ci-dessous avec une flèche noire.

Dès lors, avec ces 8 sommets et cette règle, on obtient le graphe complet formé de 8 sommets et 16 flèches :

A quoi cela sert-il ? Dans un tel graphe, un circuit qui passe au plus une fois par chaque sommet et revient à son point de départ permet de faire un collier ayant les propriétés désirées. Par exemple on peut faire le circuit

qui donne un collier de quatre perles rouge-rouge-rouge-noire dans lequel toute position est repérée de façon unique par la suite des trois couleurs consécutives.
Maintenant, pour avoir un collier de huit perles, il faut trouver un chemin qui passe une et une seule fois par chacun des huit sommets du graphe. C’est un théorème (pas si évident [5]) qu’un tel chemin existe. Par exemple, ici, il suffit de parcourir la « circonférence » dans le sens des aiguilles d’une montre comme ci-dessous :

Le circuit passant par chaque sommet, on rencontre chaque configuration de 3 perles. La suite de couleurs correspondant à ce chemin (en commençant avec la flèche noire au sommet) est noir-rouge-noir-noir-noir-rouge-rouge-rouge qui correspond exactement à notre premier collier ! Ainsi, construire un collier revient à se balader (correctement) dans un graphe. Cerise sur le gâteau, les spécialistes de la théorie des graphes vous diront qu’il existe une procédure automatique et rapide (un algorithme) pour trouver un circuit convenable.

Pour aller plus loin

En théorie des graphes, on dit que les graphes construits ci-dessus sont eulériens : il existe toujours un circuit passant par chaque sommet une et une seule fois. On peut montrer que les graphes de de Bruijn sont aussi hamiltoniens : il existe toujours un circuit passant par chaque « flèche » une et une seule fois.

Remarque historique

La construction des graphes présentés ici est souvent attribuée à N. G. de Bruijn. Cependant, ce dernier a reconnu que la paternité revenait à C. Flye Sainte-Marie en 1894. On notera que de Bruijn fut l’un des pionniers des systèmes formels de traitement de preuves dans les années 1960.

Post-scriptum :

Merci à Maxime Bourrigan pour avoir retravaillé les illustrations.
Et à tous les relecteurs (Christophe Boilley, Emeric Bouin, Creux, Pierre D, Étienne Calais, Avner Bar-Hen) pour leurs commentaires et suggestions.

Notes

[1Je peux sans problème l’affirmer : ce tour n’est pas de moi ! Il m’a été montré par Raphaël Jungers qui, lui-même, s’inspirait d’une prestation de Persi Diaconis. cf. l’excellent ouvrage (en anglais) Magical Mathematics : The Mathematical Ideas That Animate Great Magic Tricks. Dans cet ouvrage, on présente d’autres tours basés sur la notion de cycle universel : on dispose d’une propriété qui caractérise univoquement la position occupée au sein du jeu.

En outre, vous verrez que je ne suis pas le seul à présenter ce tour, vous en trouverez aussi une présentation ici avec un autre arrangement de cartes.

[2Une coupe n’est qu’une « permutation circulaire particulière » dans laquelle on ne modifie pas l’ordre relatif des cartes.

[3Pour ma part, lorsque je réalise ce tour, j’utilise comme assistant un petit programme informatique dans lequel est encodée la liste ordonnée des cartes.

[4Il serait intéressant de pouvoir compter le nombre de colliers ayant la propriété voulue et le comparer au nombre total de colliers que l’on peut construire.

[5Pour les spécialistes : Il est assez facile de voir que ces graphes orientés sont eulériens. Ils sont connexes et le demi-degré entrant de chaque sommet est égal à son demi-degré sortant. Voir, par exemple, le livre J.-P. Allouche, J. Shallit, Automatic sequences, p. 323. Ensuite, si le graphe pour les configurations de longueur n est eulérien, alors on en déduit que celui pour les configurations de longueur n+1 est hamiltonien. On pourra regarder l’article original, N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch. Proc. 49 (1946).

Partager cet article

Pour citer cet article :

Michel Rigo — «La magie des colliers de perles de Nicolaas Govert de Bruijn» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • La magie des colliers de perles de Nicolaas Govert de Bruijn

    le 30 septembre 2014 à 00:19, par amic

    Je pense qu’il y a une petite inversion entre eulérien et hamiltonien dans le paragraphe « pour aller plus loin »…

    Répondre à ce message
  • La magie des colliers de perles de Nicolaas Govert de Bruijn

    le 14 octobre 2014 à 02:08, par Dasson

    Merci pour ces eplications claires qui m(ont permis un essai de présentation en FLASH :
    http://rdassonval.free.fr/flash/mag...
    En test...

    Répondre à ce message
  • La magie des colliers de perles de Nicolaas Govert de Bruijn

    le 15 octobre 2014 à 16:14, par Monique Pencréach

    Votre article est tres agreable, notamment avec l’analogie des colliers de perle.
    Pourquoi n’y a t il aucune formule de probabilites ou combinatoire ?

    bien cordialement
    Monique Pencréach

    Répondre à ce message
  • Deux propriétés du graphe

    le 6 novembre 2014 à 22:27, par thomisus

    Dans un tel graphe, un circuit qui passe au plus une fois par chaque sommet et revient à son point de départ permet de faire un collier ayant les propriétés désirées.

    Pour me convaincre de tout ça j’avoue qu’il m’a fallu étudier le graphe de plus près.

    Propriété 1 : tous les chemins de longueurs 3 qui arrivent à un même sommet sont identiques. Par chemins identiques nous entendons des chemins qui passent par les mêmes couleurs de flèches dans le même ordre. D’ailleurs nous retrouvons les 3 couleurs utilisées dans les 3 perles du sommet atteint. La couleur de la première flèche utilisée est la même que la couleur de la première perle. La couleur de la deuxième flèche utilisée est la même que la couleur de la deuxième perle. Enfin la couleur de la troisième et dernière flèche utilisée est la même que la couleur de la troisième et dernière perle.

    Propriété 2 : deux chemins de longueurs 3 qui arrivent à deux sommets différents sont différents. C’est-à-dire qu’ils ne n’utilisent pas la même séquence de couleur des flèches. Comme les séquences de couleur des flèches sont résumées par les couleurs des trois perles du sommet, que tous les sommets ont des séquences de trois perles différentes et que nous avons choisis deux sommets distincts, nous obtenons bien cette propriété.

    Si dans notre balade dans le graphe, nous passons deux fois par un même sommet, d’après la propriété 1, nous aurons donc deux fois la même séquence de flèches. Nous loupons l’objectif de nous repérer dans le collier par une séquence unique. Il ne faut donc pas passer deux fois par le même sommet.

    Dans un circuit tous les sommets sont des arrivées de chemins de longueurs 3. La propriété 2 s’applique donc à tous les couples distincts de sommets. Les chemins de longueur 3 qui amènent à chaque sommets sont donc uniques.

    Dans un circuit qui ne se recoupe pas nous obtenons donc bien la propriété recherchée.

    Espérant avoir apporté plus d’éclaircissements que de complications ou d’erreurs.

    Alexandre

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM