Dans la prison centrale de Sikinia, il y a 30 cellules numérotées 1, 2, 3, ... , 30, toutes occupées. Les portes des cellules peuvent être dans deux états: ouvertes ou fermées. On peut passer d’un état à l’autre en faisant faire un demi-tour au bouton de la porte. Au moment où commence l’histoire, toutes les portes sont fermées.
Pour fêter le vingtième anniversaire de la république de Sikinia, le président décide d’une amnistie. Il donne au directeur de la prison les ordres suivants:
"Tournez successivement d’un demi-tour les boutons:
- de toutes les portes,
- puis d’une porte sur deux, à partir de la deuxième,
- puis d’une porte sur trois, à partir de la troisième,
- puis d’une porte sur quatre, à partir de la quatrième.
Continuez ainsi jusqu'à la dernière cellule.
Libérez alors les prisonniers dont la porte de la cellule est ouverte."
Pour des raisons de sécurité, le directeur de la prison aimerait connaître à l’avance quels seront les prisonniers libérés. Pouvez-vous l’aider?
Vous séchez? La solution!
(Problème tiré de Elements of mathematics, 1975, St-Louis (Missouri))
Publié