La traversée du Père Noël

L'énigme

Lors de sa tournée, le père Noël arrive au manoir de Monsieur Math. En sortant du foyer de la cheminée, il remarque que le plancher est divisé en carreaux hexagonaux portant des numéros. Un écriteau près du foyer donne cet avertissement :

Avis aux intrus et au père Noël, le plancher de cette salle est piégé. Pour vous rendre au sapin, vous devez emprunter uniquement les carreaux dont le produit total donne 22!, les autres étant des pièges.

Le Père-Noël sait que 22! est la factorielle de 22, soit le produit des entiers de 1 à 22! (1×2×3×4×5×…×21×22), mais il ne sait pas quel chemin prendre.

Aidez le père Noël à se rendre au sapin en lui indiquant les carreaux qu'il doit emprunter, sachant qu'il ne peut pas sauter à cause de sa hotte pleine de cadeaux.

Tiré du site web Le blog-notes mathématique du coyote par Didier Müller

La solution

Le chemin que doit emprunter le Père Noël est :

50 – 6 – 11 – 19 – 49 – 36 - 3 – 12 – 8 – 33 – 24 – 2 – 18 – 34 – 26 – 1 – 14 – 25 – 4

À gauche, le dallage avec la résolution et à droite la décomposition de facteurs de certaines dalles.

Rappelons que 22 s’écrit comme :

1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22

Et se décompose en facteurs premiers comme :

2 x 3 x 5 x 7 x 11 x 13 x 17 x 19

Le Père Noël devra donc éviter :

• Tous les nombres premiers supérieurs à 22, soit (par colonne) 41, 23, 97, 53, 31 et 43 (cases rouges)

• Tous les nombre comportant un nombre premier supérieur à 22 dans leur décomposition en facteurs premiers, soit 46 = 23 x 2, 23, et 69 = 23 x 3 (cases rouges avec les nombres bleus)

Par conséquent, la seule manière de commencer le chemin consiste à passer par 50 et 6 et la seule manière de le finir consiste à passer par 25 puis 4.

Or, 50 = 5 x 5 x 2 et 25 = 5 x 5. Ainsi en passant par 50 et 25, on obtient les quatre 5 présents dans la décomposition de 22! en facteurs premiers, soit les 5 présents dans 5, 10, 15 et 20. (En fait, si on considère 50, 6, 25 et 4, on obtient les facteurs premiers de 5, 10, 15 et 20 plus un facteur 2.) Le Père Noël devra par conséquent éviter aussi toutes les autres cases contenant des 5 dans leur décomposition en facteurs premiers, soit 10, 20, 35, 30, 5 et 45 (cases magenta).

Deux autres cases sont aussi obligatoires sur le passage du Père Noël, le 11 et le 33. En effet, ce sont les seuls multiples de 11 et il y a exactement deux 11 dans la décomposition de 22! (présents dans 11 et 22).

Conséquence du passage par 11, le Père Noël devra obligatoirement passer par le 19. Comme il n’y a qu’un 19 dans la décomposition de 22!, on peut barrer 57 = 3 x 19, 38 = 2 x 19 et 76 = 4 x 19.

En barrant le 57, le 17 devient inatteignable. Il faut donc trouver un autre 17 dans les facteurs des nombres restants. Le seul 17 qui apparaît est dans 34 = 2 x 17. Le Père Noël devra donc passer par là.

Comme le Père Noël passe par 19, il doit passer par conséquent par 49 = 7 x 7. Il y a exactement trois 7 dans la décomposition de 22!, à savoir dans 7, 14 = 2 x 7 et 21 = 3 x 7. Il faut donc ajouter au parcours un seul autre facteur 7. Les deux tuiles adjacentes au 25 par lequel le Père Noël doit passer comportent justement un facteur 7 (14 = 2 x 7 et 21 = 2 x 7). Au vu des tuiles restantes, le seul choix possible et de passer par le 14. Le Père Noël peut dès lors éliminer toutes les autres tuiles comportant un 7 dans leur décomposition, à savoir 21 = 3 x 7, 42 = 6 x 7, 63 = 9 x 7 et 28 = 4 x 7.

En éliminant 28, le 13 se retrouve inatteignable, il faut donc que le Père Noël trouve un autre facteur 13. Le 13 est présent dans la décomposition de 26 = 2 x 13 et de 56 = 4 x 13. Au vu de la position du 56, c’est le 26 que devra choisir le Père Noël.

Finalement, les tuiles restantes permettent de récupérer tous les derniers facteurs de 22! Ceci montre que le chemin est unique.

Mathscope, Université de Genève, RTS Découverte