MULTIPLIER, PUIS DIVISER PAR DEUX

Voici un amusant petit problème à poser à vos amis.

Vous prenez une feuille de papier de format ordinaire. Vous faites remarquer qu’on peut convenir qu’elle a un dixième de millimètre d’épaisseur. Vous la pliez en deux par son milieu et expliquez que vous avez désormais entre les mains un petit cahier constitué de deux feuilles et quatre pages, lequel a donc deux dixièmes de millimètres d’épaisseur.

Vous pliez une fois de plus et faites alors remarquer que votre petit cahier a désormais quatre dixièmes de millimètres d’épaisseur. Vous dépliez ensuite lentement votre cahier, pour revenir à la feuille initiale. Pendant ce temps, vous dites : «Chaque pli ne m’a guère pris plus d’une seconde et si j’avais continué pendant une minute, j’aurais certainement pu faire, disons, 50 plis. Mais je ne veux pas vous faire perdre de temps.»

Vous posez ensuite aussitôt la question suivante: «Supposons cependant que j’aie continué jusqu’à 50 plis, quelle aurait selon vous été l’épaisseur du petit cahier que j’aurais ainsi confectionné devant vos yeux en moins d’une minute?»

Les réponses varieront beaucoup, mais vous aurez typiquement les suivantes: 5 centimètres (50 fois 1 dixième de millimètre!); plusieurs centimètres; un mètre; plusieurs mètres; et, chez ceux et celles qui se méfieront avec raison de la vitesse à laquelle croissent ces progressions géométriques, des estimations parlant de «la hauteur d’un building», voire encore plus haut.

Mais peu de gens vont imaginer le résultat auquel on parviendrait si on pouvait réaliser cette expérience — ce qui est impossible étant donné qu’après 7 ou 8 plis, on ne peut physiquement la poursuivre. Ce résultat? 122 millions de kilomètres! Quelque chose comme les deux tiers de la distance de la Terre au Soleil !

Ce résultat fait bien voir l’extraordinaire vitesse de ces progressions où on multiplie à chaque fois le résultat par deux.

On l’aura deviné : quelque chose d’aussi spectaculaire et étonnant peut par définition être obtenu en … divisant par deux.

Prenez par exemple un numéro de téléphone à 7 chiffres, n’importe lequel. Le plus grand de ces numéros sera : 999-9999. En combien de questions pensez-vous pouvoir identifier, avec certitude, le numéro d’une personne que vous venez de rencontrer.

La réponse, inattendue, est 24 et elle repose sur un principe de classification binaire, par laquelle on «divise par deux», si je peux dire.

Avez-vous une idée de la manière de procéder?



RÉPONSE

Supposons qu’on veuille identifier un élément parmi deux (1 ou 2). On voit immédiatement qu’une seule question suffira, nommément : «Est-ce 1?».

Si on veut cette fois identifier un élément parmi 4 (1, 2, 3, 4), deux questions suffiront, mais à condition de diviser par deux notre ensemble — c’est justement cela la classification binaire. Par exemple : «Est-ce un nombre plus grand que 2?». Que la réponse soit oui ou non, une dernière question permet de l’identifier.

Selon le même principe, si on veut identifier un élément parmi 8, trois questions suffiront. «Est-ce un nombre plus grand que 4?» Puis, selon la réponse : «Est-ce un nombre plus grand que 2?» ou «Est-ce un nombre plus grand que 6?».

Si on généralise cette idée, on trouvera que n questions suffisent pour identifier un élément particulier d’un ensemble de 2 n éléments.

Considérons notre numéro de téléphone. 2 23 donne 8 388 608. C’est énorme et très intéressant pour ce qu’on cherche, mais ça ne permet d’identifier aucun des numéros de téléphone depuis 838- 8609 jusqu’à 999-9999. Considérons donc 2 24.

Cette fois, cela donne : 16 777 216, ce qui est plus qu’il ne nous faut. Il s’ensuit qu’avec 24 questions au maximum, en procédant par classification binaire, on est assuré de trouver le numéro de téléphone à 7 chiffres d’une personne.

Essayez-le avec une personne dont vous ne connaissez pas le numéro de téléphone.