Problème N°4 : un roi, proposé par Ahmed Zahidi

Un Roi accorde une amnistie au profit de certain prisonniers à l'occasion d'une fête religieuse...Pour la prison X , le roi décide de libérer certains prisonniers qui seront déterminés comme suit:
Dans la prison X , il y a 1000 prisonniers dans 1000 cellules,
surveillés par 1000 gardiens.
-le 1^er gardien ouvre toutes les cellules
-le 2^èmegardien ferme toutes les cellules
-le 3^ème gardien ouvre les cellules multiples de 2
-le 4^ème gardien change d'état les portes des
cellules multiples de 3 (changer d'état de la porte de la cellule cad si elle est ouverte elle se referme ; si elle est fermée elle s'ouvre)
-le 5^ème gardien change d'état les portes des
cellules multiples de 4...

Et ainsi de suite jusqu'au millième gardien...

Alors le Roi amnistie les prisonniers qui seront libérés cad dont les portes de leurs cellules seront ouvertes en fin de compte.

Question: COMBIEN DE PRISONNIERS DE LA PRISON X SERONT AMNISTIES PAR LA GRACE ROYALE POUR LA PRISON X.

10 bonnes réponses de : Alain Debreil (13/06/01), Guy Philippe (20/04/01), Pierre Gramme (03/04/01), David Loyer (29/03/01), Frédéric Morlot (21/03/01), Julien Santini (18/03/01),  Louis Dupaigne (22/02/01), Jean Jacquelin (21/02/01), J-P Houbard (20/02/01) et Pierre Renfer (14/12/00).

• Solution d'Alain Debreil :
  Bonjour, Eliminons le gardien nø1, et renumérotons les gardiens en commençant par 1,
  jusqu'a 999. Au départ toutes les cellules sont ouvertes. La cellule n changera d'état par les gardiens de numéro un diviseur de n.
  Une cellule n terminera fermée si elle subit un nombre impair de changements
  d'état, c'est à dire si n admet un nombre impair de diviseurs.
  Or si n = p1^a1.p2^a2...pk^ak est la décomposition de n en facteurs premiers,
  le nombre des diviseurs de n est (a1+1).(a2+1)...(ak+1)
  Ce nombre sera impair si et seulement si chaque (ai+1) est impair c'est …
  dire chaque ai est pair.
  Cela est équivalent à "n est le carré d'un entier". Il y a 31 carrés inférieurs à 1000 (31^2 = 961 < 1000 < 32^2 = 1024)
  Il faut maintenant considérer la 1000-ème cellule
  Comme 1000 n'est pas carré le gardien nø 1000 ouvrirait la cellule, mais dans notre renumérotation, il n'y a pas de gardien numéro 1000. Cette cellule 1000 reste donc fermée.
  Finalement, toutes les cellules finissent ouverte, sauf celles de rang carré et sauf la cellule 1000, ce qui fait 31 + 1 = 32 cellules restant fermées. Donc 1000 - 32 = 968 prisonniers sont libérés.
  S'il faut montrer la formule sur le nombre de diviseurs de n,
  en voici une démonstration:
  Définitions: Notons D(n) l'ensemble des diviseurs de n, |D(n)| son cardinal et notons m|n pour m divise n.
  Lemme1: Si pgcd(m,n)=1 alors D(m.n) = {mi.nj / mi dans D(m) et nj dans D(n)}
  preuve: Soit E = {mi.nj / mi dans D(m) et nj dans D(n)}
  Pout tout mi.nj dans E mi|m et nj|n donc mi.nj|m.n ==> E inclus dans D(m.n)
  Réciproquement: soit x dans D(m.n) et p un diviseur premier de x,
  x = p^a.y avec y premier avec p et a > 0; comme m et n sont premiers entre eux, p^a divise l'un de m ou n et seulement celui-ci.  Alors x se décompose en:
  x = Prod(pi^ai \ pi^ai divise m) . Prod(pj^aj \ pj^aj divise n)
  Or par construction Prod(pi^ai \ pi^ai divise m) est dans D(m) et
  Prod(pj^aj \ pj^aj divise n) est dans D(n) et donc x est dans E
  Finalement D(m.n) = E.
  Lemme2: Si pgcd(m,n)=1 alors |D(m.n)| = |D(m)|.|D(n)|
  preuve: D(m.n) = {mi.nj / mi dans D(m) et nj dans D(n)}, il faut montrer que
  les mi.nj sont tous distincts.
  Si mi.nj = m'i.n'j, m et n étant premiers entre eux, mi ne divise pas n'j,
  donc divise m'i; pareillement m'i divise mi donc mi = m'i.
  De la même manière nj = n'j et finalement les produits mi.nj sont tous
  distincts dans D(m.n).
  Lemme3: D(1) = {1}; D(p) = {1,p}; D(p^n) = {1,p,...,p^(n-1),p^n}
  |D(1)| = 1; |D(p)| = 2; |D(p^n)| = n+1
  preuve: Les diviseurs de p^n sont toutes les puissances inférieures à n de p
  Lemme4: Si n = p1^a1.p2^a2...pk^ak,
  
• Solution de Guy Philippe :
  
  J'ai découvert ce site récemment et avec intérêt car j'y ai trouvé des
  questions fort passionnantes comme celle des prisonniers.Voici ma solution
  Oublions provisoirement 1000 pour s'intéresser au cas général de n
  prisonniers(n>=2)
  Notons c le nombre d'entiers <n qui sont des carrés.
  Exemples: pour n=6 on a c=2
  pour n=9 on a c=2
  pou n=1000 on a c=31
  Remarque fondamentale(ici!)
  Les diviseurs d'un entier vont par 2 (diviseurs jumeaux)
  2.9=18 ; 2 et 9 sont diviseurs jumeaux (faux jumeaux) de 18
  5.5=25 ; 5 et 5 sont diviseurs jumeaux (vrais jumeaux) de 25 car est le carré
  de 5
  dans l'ensemble des diviseurs d'un entier les diviseurs faux jumeaux
  comptent pour 2
  alors que les vrais jumeaux comptent pour 1 .
  D(18)={1,2,3,6,9,18} card(D(18)) =6
  D(25)={1,5,25} card(D(25))=3
  "Des lors on comprend que si k est un carré alors card(D(k)) est impair et si
  k n'est pas un carré alors card(D(k)) est pair "
  Après le passage du gardien 1 toutes les portes sont ouvertes;c'est l'état
  initial.
  Pour chaque porte k=1 à n-1 tout diviseur d de k est =< n-1 donc d sera
  sollicité par le gardien d+1=2 à n.
  D'où chaque porte k= 1 à n-1 va changer d'état un nombre de fois égal à
  card(D(k)).
  Par conséquent
  si k n'est pas un carré alors car(D(k)) est pair et à la fin la porte k est
  ouverte
  si k est un carré alors card(D(k)) est impair et à la fin la porte k est
  fermée.
  Parmi les portes de 1 à n-1 ,comme il y a c carrés ,il y aura à la fin n-1-c
  portes ouvertes .
  Quant à la dernière porte,la nième
  si n est un carré card(D(n)) est impair et tous les diviseurs de n ,sauf n
  ,ont été sollicités par un des gardiens 1,2,3......ou n ce qui donne un
  nombre pair de changements d'état et la porte n ouverte à la fin .
  Le nombre de prisonniers graciés sera n-1-c+1=n-c si n est un carré.
  Si n n'est pas un carré card(D(n)) est pair et n sera le seul diviseur de n
  non sollicité par un gardien d'où un nombre impair de changements d'état et
  la porte n sera ainsi fermée.
  Le nombre de prisonniers graciés sera n-1-c si n n'est pas un carré
  Retour à n=1000 alors c=31 et comme 1000 n'est pas un carré la réponse est
  1000-1-31=968 prisonniers graciés
  Bien à vous
  
  Solution de David Loyer :
  
  a) un nombre subit autant de permutations qu’il a de multiple.

  Si le nombre de ces permutations est impair la cellule est ouverte, sinon fermée

  b) il faut donc déterminer combien de nombres ont un nombre de multiples pair, combien impair

  c) tous les nombres ont un nombre de multiples pair, ce qui tombe sous le sens.

  d) seuls dérogent à la règle les nombres élevés au carré, puisque la racine se multiplie elle-même sans aller seulement par couple comme dans les autres cas

  II a) si le nombre des permutations est impair, la cellule est ouverte, sinon fermée.

  b) mais la série commence par les multiples de 2 et ignore les multiples de 1 de sorte que chaque cellule est privée de l'une de ses permutations. Il s'ensuit que, en enlevant un multiple commun à toutes les cellules, toutes celles qui en possédaient un nombre pair en possède un nombre impair et réciproquement.

  c) donc, toutes les cellules seront ouvertes sauf les carrés des nombres 1 à 31. La première cellule étant fermée pour d'autres raisons soit dit en passant., ce qui nous donne 31 cellules fermées

  d) dernière chose: le gardien n change d'état la cellule n-1. Par suite le millième gardien s'occupe de la 999eme cellule et non de la millième. La millième cellule ne change pas d'état avec elle-même, possède un nombre pair de permutations, comme n'importe quel nombre, elle n'est pas un carré. Elle reste donc fermée

  Il y a donc 1000-31 -1= 968 cellules ouvertes

• Solution de Frédéric Morlot :
  
  Le n-ème prisonnier (1<=n<=1000) est amnistié ssi sa cellule est changée
  d'état un nombre impair de fois, ssi sa cellule est changée un nombre pair
  de fois par les gardiens 2 à 1000.
  Or sa cellule est changée d'état par le k-ème gardien (3<=k<=1000) ssi
  (k-1) | n.
  Pour k=2, c'est encore vrai:sa cellule est effectivement changée d'état par
  le deuxième gardien.
  Finalement, un prisonnier est amnistié ssi son numéro a un nombre pair de
  diviseurs entre 1 et 999.
  Dénombrons plutôt les prisonniers non amnistiés dont le numéro est entre 1
  et 999.
  Leur numéro comporte un nombre impair de diviseurs donc ce sont les carrés
  entre 1 et 999(cela se voit à partir de la décomposition en facteurs
  premiers par exemple: le nombre de diviseurs de p1^a1*p2^a2*...*pk^ak est
  (a1+1)(a2+1)...(ak+1) )
  Il y en a donc 31;quant au millième, il a 15 diviseurs entre 1 et 999 donc
  il est condamné.
  Finalement, le nombre cherché est:
  1000-31-1=968.
  
  Solution de Julien Santini :
  
  Dans le cas le plus général, notons n le nombre de prisons, n>=2.
  Soit i entier naturel tel que n>i>=1. On peut faire alors le constat
  suivant: si le nombre des diviseurs positifs de i est pair, alors la ième
  cellule sera ouverte. Sinon, elle restera fermée.
  Pour le cas de la nième prison (i=n) si le nb des diviseurs positifs de n
  est pair alors la nième cellule restera fermée, sinon elle sera ouverte. (en
  effet le nième gardien change l'état des cellules multiples de (n-1)
  uniquement.... or n est diviseur de n, d'où la soustraction d'un cas).
  D'après le théorème de décomposition, un nombre i>=1 a la somme de ses
  diviseurs positifs qui est paire ssi peut s'écrire sous la forme i=
  (a_1)^(b_1)*...* (a_i)^(b_i) avec pour tout i, b_i est pair et non nul, ie i
  est un carré.
  Conclusion:
  Seront libérés:
  [n-E(sqrt(n))-1] prisonniers.
  Application numérique: n=1000 cellules
  Alors on libérera: 1000-E(sqrt(1000))-1=968 prisonniers.
  
  Julien Santini,
  Lycée Lacordaire
  Solution de Jean Jacquelin :
  
  Les cellules dont le numéro est un carré restent fermées (1, 4, 9 etc., 961) soit 31 cellules. Mais le 1000ième gardien ouvre la 999ième cellule. La 1000 cellule reste donc fermée. Donc au total 32 cellules sont closes à la fin. Résultat: 968 prisonniers sont libéres.

  Solution de Pierre Gramme :
  
  Considérons une porte quelconque, celle de la n-ème cellule. Les seuls gardiens qui changeront son état seront le premier et ceux dont le numéro est un multiple de n augmenté de 1. Les prisonniers libérés seront donc ceux dont le numéro de cellule a un nombre pair de diviseurs <1000. Il s'agit de tous les nombres qui ne sont pas des carrés parfaits, sauf 1000. Le nombre de libérés est donc

  999-31=968

  (car 31²<1000<32²)

•