L’énigme des pèlerins (a)

L‘énigme qui suit est une ancienne énigme : elle a été publiée en 1907, créée par Henry Ernest Dudeney et inspirée par les célèbres « Canterbury Tales » de l’écrivain anglais Geoffrey Chaucer (1340-1400) .

Un monastère doit recevoir des pèlerins. Son dortoir contient deux étages avec 8 chambres chacun, l’escalier se trouvant au centre de l’ensemble. Le prieur a exigé que chaque chambre soit occupée par au moins 1 personne, et au maximum 3 personnes. Chaque côté (Nord, Est, Sud, Ouest) de chaque étage doit avoir exactement 11 pélerins (en comptant les deux étages). En outre, il doit y avoir exactement 2 fois autant de pèlerins au premier étage qu’au rez-de-chaussée.

Les moines étant très astucieux, ils parviennent à planifier le logement pour tous les pèlerins annoncés. Mais, quand les pèlerins arrivent, on découvre qu’il y en a 3 de plus que prévu. Heureusement, les moines trouvent une nouvelle solution qui, elle aussi, satisfait toutes les contraintes.

Quel était le planning initial d’occupation des chambres ?
Quel est le planning final ?

Des premiers éléments de réflexion…

Pour vous mettre un peu sur la voie, on sait que le nombre de pèlerins est compris entre 24 (1 par chambre en bas et 2 par chambre en haut) et 36 (3 par chambre en haut et en moyenne 1,5 par chambre en bas). On sait aussi que c’est un multiple de 3, vu qu’il y en a 2 fois plus en haut qu’en bas. Vous voyez, avec un peu de bon sens, on se limite déjà à 5 cas possibles : 24, 27, 30, 33, 36.

Dans l’exemple ci-dessous, nous avons mis en place une solution qui aboutit au total de 27 pèlerins mais qui ne satisfait pas les contraintes en D21:D24 où l’on devrait avoir un total de 11 à chaque fois. En revanche, toutes les autres contraintes sont satisfaites…