L’escalier : On peut monter un escalier une ou deux marches à la fois. La figure ci-dessous montre un exemple.

De combien de façons différentes peut-on monter un escalier de une marche ? de deux marches ? de trois marches ? de quatre marches ? de cinq marches ?

De combien de façons différentes peut-on monter un escalier de 20 marches ?

Amnistie : Dans la prison centrale de Champ-Dolon, il y a 250 cellules numérotées 1, 2, 3, …, 250, 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 Genève, 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 les prisonniers dont la porte de la cellule est ouverte. »

Pour des raisons de sécurité, le directeur de la prison vous demande de lui fournir un rapport dans lequel figurera :

a)       le nombre de prisonniers qui seront libérés,

b)      la liste des cellules qu’ils occupent et

c)       la description la plus claire possible de votre méthode afin qu’il puisse vérifier votre liste !