Answered

Dans un donjon, vingt cellules numérotées de 1 à 20 sont fermées à clé.Ces cellules s'ouvrent et se ferment en un tour de clé.
Alors que les prisonniers dorment à poings fermés, un premier gardien, qui les pensaient ouvertes, met un tour de clé à toutes les cellules.
Peu aprés, un deuxiéme gardien met un tour de clé à toutes les cellules dont le numéro est un multiples de 2.
Arrive ensuite un troisiéme gardien qui met un tour de clé à toutes les cellules dont le numéro est un multiple de 3.
Et ainsi de suite.....
Au final, vingt gardiens se sont succédés!

a) Quels sont les numéros de cellules dont les prisonniers vont facilement pouvoir s'évader ?
b) Reprendre le même probléme avec 500 cellules et 500 gardiens !! Justifie ta réponse.

Sagot :

Chaque porte reçoit autant de tours de clef que le nombre de diviseurs de son numéro. 
Tout nombre peut s'exprimer comme p1e1 * p2e2 * p3e3 * ... ou les p sont des nombres premiers. 
Un diviseur de ce nombre s'écrira p1f1 * p2f2 * p3f3 * ... 
L'exposant f1 peut être choisi parmi les nombres de 0 à e1 (car n0 = 1), soit (e1+1) exposants possibles. 
L'exposant f2 peut être choisi parmi les nombres de 0 à e2, soit (e2+1 exposants possibles). 
Remarque : si tous les f choisis sont 0, le diviseur sera 1. 
En tout : (e1+1) * (e2+1) * (e3+1) * ... diviseurs. 
Supposons que le numéro soit un carré : tous les e sont pairs; tous les (e+1) sont impairs; le produit des (e+1) sera impair et il y a un nombre impair de diviseurs; à la fin, la porte sera ouverte. 
Supposons que le numéro soit un carré : il y a au moins un e impair, au moins un (e+1) pair; le produit des (e+1) sera pair et il y a un nombre pair de diviseurs; à la fin, la porte sera fermée. 
Avec 500, les portes ouvertes sont 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 ET 484.