Le problème des 1 000 portes en Algobox. publié le 29/01/2010

Problème vu lors de la formation "logiciels pour l'algorithmique"

Le problème est le suivant :

Vous êtes face à 1 000 portes (numérotées de 1 à 1 000) toutes fermées.

Imaginez l’opération suivante.

  • On ouvre toutes les portes dont le numéro est un multiple de 1 ;
  • on ferme toutes celles dont le numéro est un multiple de 2 ;
  • on change d’état (fermeture pour une porte ouverte et ouverture pour une fermée) toutes celles dont le numéro est un multiple de 3 ;
  • ... et ainsi de suite jusqu’à 1 000.

Empruntez la 23ème porte qui serait ouverte et vous serez au paradis.

Premier algorithme (ALG de 3.5 ko)

Cet algorithme demande le numéro de la porte et répond son état final (fermée ou ouverte).

Deuxième algorithme (ALG de 4.1 ko)

Cet algorithme demande le nombre total de portes et affiche la liste des portes finalement ouvertes.

Pour répondre à la question, le deuxième algorithme suffit.

Si on veut prouver qu’une porte est finalement ouverte si et seulement son numéro est un carré (cela quel que soit le nombre total de portes), il faut alors faire une démonstration.

Démonstrations (PDF de 64.5 ko)

Deux démonstrations, une de niveau troisième et une de niveau TS spé Math.