Entretien d’embauche

“Le Nombre imaginaire” ou les mathématiques comme terrain de jeu où l’imagination seule fixe les limites.

Un aspect de la culture geek d’Internet que l’on peut juger amusant ou effrayant est la manière dont ses membres se cooptent. S’il est un domaine où la sélection par les maths est reine, c’est celui-là. Google (comme d’autres acteurs) utilise ainsi régulièrement des techniques de recrutement du type jeu de piste : une énigme est posée à la communauté internet, et les quelques petits génies qui la résoudront en premier se verront envoyer un lien secret leur offrant la possibilité d’en résoudre d’autres, puis (après entretien de personnalité, on ose l’espérer) d’être recrutés.

Voici une très jolie énigme posée régulièrement, paraît-il,  en entretien d’embauche par l’un des acteurs majeurs de l’Internet. Partant du principe que le lecteur de délibéré n’est que peu susceptible de se porter candidat chez eux, je ne me sens guère de scrupules à vous en proposer énoncé et solution.

Les entretiens sont souvent des marathons où l’impétrant, accueilli dans un bureau pour l’après-midi,  rencontre une succession de personnes qui viennent l’interroger. À la fin d’un de ces entretiens, l’interviewer tend un paquet de cartes au candidat en lui demandant d’en choisir cinq et de les lui donner. Il choisit ensuite l’une de ces cinq cartes et la rend au candidat, en lui demandant de la cacher. Puis il dispose les quatre autres, faces découvertes, en ligne sur la table. Il demande alors au candidat de faire signe à l’interviewer suivant qui attend déjà derrière la porte. Ce dernier entre dans le bureau, salue le candidat, jette un coup d’œil sur la table, et lui dit “la carte qui vous reste est la dame de Cœur. Ma première question pour vous est : comment mon collègue et moi avons-nous fait ce tour de magie ?”.

On peut imaginer que cette scène soit passablement déstabilisante pour un candidat déjà stressé. Cependant, il y a derrière un bien joli problème à résoudre. Sachant que le candidat a choisi librement cinq cartes du paquet, et que les deux interviewers n’ont pas communiqué entre eux, comment se sont-ils débrouillés, l’un pour choisir une carte parmi ces cinq, et l’autre pour la deviner, au seul vu d’une rangée de quatre autres cartes ? Je vous laisse y réfléchir un petit moment.

La clé de ce problème, c’est pour le premier interviewer de coder d’une manière ou d’une autre l’identité de la carte secrète au moyen des quatre cartes visibles, pour que le deuxième puisse ensuite la décoder. Or ce n’est pas évident. La carte cachée pourrait être n’importe quelle autre que ces quatre là, donc il y a quarante-huit possibilités (nous parlons d’un jeu de 52 cartes, sans joker). Par ailleurs, le premier interviewer n’a aucun contrôle sur les cinq cartes dont il dispose et qui ont été choisies par le candidat : elles pourraient, par exemple, être toutes de la même couleur ; ou bien elles pourraient consister en un carré d’as et un deux. Il n’y a donc pas beaucoup de possibilité de transmettre une information à coup sûr en utilisant quatre de ces cartes.

Il est cependant toujours possible de comparer des cartes entre elles selon un critère de valeur qui combine leur couleur et leur rang. On peut, par exemple, décider qu’un pique vaut toujours mieux qu’un cœur, qui bat un carreau, qui est meilleur qu’un trèfle ; et que dans une même couleur, le roi bat la dame, la dame le valet, et ainsi de suite jusqu’au deux qui bat le un.

On peut alors coder de l’information dans l’ordre des cartes visibles. Si elles sont ordonnées de gauche à droite par valeur décroissante, par exemple, cela donnera une autre information que si elles sont ordonnées en sens inverse. Il y a ainsi vingt-quatre manières différentes de placer quatre cartes en ligne : c’est bien… mais ce n’est pas assez pour coder les quarante-huit possibilités. Or, nous savons par hypothèse qu’il existe une solution. Nous devons donc en déduire qu’il existe un élément de l’énoncé que nous n’avons pas encore exploité. Il doit être possible de l’utiliser pour passer une information supplémentaire qui ne se limite pas à l’ordre des quatre cartes, et qui permette de préciser l’identité de la carte cachée. Comment cette information pourrait-elle être transmise ? Si elle n’est pas liée à l’ordre des cartes visibles, elle doit concerner une propriété de l’une d’entre elle – sa couleur, ou peut-être son rang. Mais comment coder une telle information, quand nous ne savons rien a priori sur les cinq cartes initialement sélectionnées par le candidat ?

La réponse est que nous ne sommes pas totalement ignorants quant à ce choix. Nous savons que le candidat  avait choisi cinq cartes. Parmi celles-ci, deux au moins étaient donc nécessairement de la même couleur. C’est un élément d’information capital. En tant que “codeur”, je vais donc choisir comme carte cachée l’une des cartes de cette couleur-là : soit la plus petite, soit la plus grande comme nous le verrons. Je placerai ensuite une autre carte de cette même couleur – la plus grande ou la plus petite – à gauche de la rangée de quatre cartes visibles. 

En voyant la rangée de cartes, mon complice connaîtra immédiatement par celle de gauche la couleur de la carte cachée. Il lui restera toutefois à en déterminer le rang ; or il devra choisir au mieux entre neuf possibilités (si toutes les cartes visibles sont de la même couleur) et au pire entre douze. Or, je ne peux plus coder que six choix possibles en choisissant l’ordre des trois cartes à droite de la rangée. Ça ne passe toujours pas ; il faut donc que j’exploite une autre information.

Cette information, c’est le rang de la carte de gauche de ma rangée. En effet, revenons à mon choix de la carte secrète. J’ai choisi une couleur pour laquelle il y a au moins deux cartes parmi les cinq. S’il y en a plus, ce qui est possible, je ne considère que la plus grande et la plus petite de ces cartes. Laquelle des deux choisir ?

Imaginons toutes les cartes d’une couleur posées en cercle : partant de l’as, on passe dans le sens des aiguilles d’une montre au deux, puis progressivement à la dame et au roi, que l’on place voisin de l’as. Ce cercle comporte treize cartes, donc aussi treize intervalles entre ces cartes. J’observe alors que je peux toujours passer d’une carte à l’autre en traversant six intervalles au maximum : si elles sont séparées de huit intervalles dans le sens des aiguilles d’une montre, par exemple, elles ne sont séparées que de cinq intervalles en passant par l’autre côté. Cela veut dire aussi que, si je m’impose de toujours me déplacer dans le sens des aiguilles d’une montre sur ce cercle, soit je peux relier la plus petite carte à la plus grande en six intervalles ou moins, soit je peux relier la plus grande à la plus petite en six intervalles ou moins. Voilà qui tombe parfaitement bien ! Car j’ai justement six possibilités de jouer sur l’ordre des trois cartes de droite dans ma rangée.

Nous tenons donc notre méthode de codage. Je sélectionne, parmi les cinq cartes choisies par le candidat, un groupe de cartes de la même couleur. Si la différence de rang entre la plus petite et la plus grande est inférieure ou égale à 6, je donne la plus grande au candidat et je place la plus petite à gauche de ma rangée de cartes. Sinon je donne la plus petite au candidat et je place la plus grande à gauche. Ainsi, si ma plus petite carte est le dix de cœur et la plus grande la dame (deux rangs au-dessus), je donne la dame au candidat ; mais si la plus petite carte est l’as de cœur et la plus grande la dame, alors je donne l’as au candidat, en notant que sur mon cercle je peux passer de la dame à l’as en franchissant deux intervalles.

Je place ensuite mes trois cartes restantes dans un ordre qui code le nombre deux, comme nous le verrons.

Mon collègue regarde la rangée de cartes. Il y voit, par exemple, le dix de cœur à gauche ; et en décodant l’ordre des trois autres cartes, il trouve le nombre deux. Il franchit alors deux intervalles dans le sens des aiguilles d’une montre sur le cercle, en partant du dix, ce qui lui donne la dame de cœur. Si, au contraire, il voyait la dame de cœur, il franchirait toujours deux intervalles dans le sens des aiguilles d’une montre, en passant par le roi puis en arrivant à l’as de cœur.

Reste à déterminer comment coder les nombres de 1 à 6 dans l’ordre des trois cartes de droite. Voici une manière de faire. Si je note 1 la carte ayant le moins de valeur (au sens où je l’ai défini plus haut), 2 celle du milieu et 3 celle ayant le plus de valeur, l’ordre dans lequel elles apparaissent dans la rangée code un nombre, par exemple 213. Il y a six nombres possibles, que je range du plus petit au plus grand : 123, 132, 213, 231, 312, 321. Le rang du nombre que j’obtiens dans cette liste me donne un nombre entre 1 et 6. On imagine bien qu’il faille un peu de pratique, mais ce n’est pas très sorcier.

La meilleure candidate, paraît-il, mit 35 minutes à résoudre ce problème. Il m’a fallu plus de temps que ça. Je ne saurai donc jamais si j’aurais été pris…

Yannick Cras
Le nombre imaginaire

Imprimer Imprimer