Le problème des portes de prison

Dans la prison centrale de Champ-Colon, il y a 10000 cellules numérotées 1 , 2 , 3 , ... , 10000, 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 Gevene, 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 combien de prisonniers seront libérés et desquels il s'agira.

Pouvez-vous l'aider ?

  Connexion