Solution au problème d'avril 2003

Voici une liste d'affirmations, numérotées de 1 à 10, permettant de trouver un nombre naturel inconnu n. Malheureusement, ces affirmations ne sont pas nécessairement vraies et, pour corser les choses, on ne dit pas lesquelles sont vraies et lesquelles sont fausses.

  1. Au moins une des deux dernières affirmations de cette liste est vraie.
  2. Ceci est soit la première affirmation vraie, soit la première affirmation fausse de cette liste.
  3. Cette liste comprend au moins trois affirmations fausses consécutives.
  4. La différence entre le numéro de la dernière affirmation vraie et le numéro de la première affirmation vraie est un diviseur de n.
  5. La somme des numéros des affirmations vraies est égale à n.
  6. Ceci n'est pas la dernière affirmation vraie.
  7. Le numéro de chacune des affirmations vraies est un diviseur de n.
  8. Cette liste comprend exactement n% d'affirmations vraies.
  9. Le nombre de diviseurs de n (les diviseurs triviaux 1 et n étant exclus) est strictement supérieur à la somme des numéros des affirmations vraies.
  10. Cette liste ne comprend pas trois affirmations vraies consécutives.

Notre problème du mois:

Que vaut n?

Solution au problème MP32

Nous avons reçu des solutions de Martín Aregami (Regina), Pierre Bornsztein (France), Normand Laliberté (Ontario), Patrick J. LoPesti (Massachusetts), Juan Mir Pieras (Espagne) et Alexander Potapenko (Russie). Notre présentation combine les idées de tous ces correspondants. On suppose le tiers exclus, c'est à dire que chaque énoncé est soit vrai, soit faux. On donne d'abord la valeur de vérité de chaque énoncé, que l'on justifiera plus bas.

  1. Au moins un des deux derniers énoncés de cette liste est vrai: Faux (A)
  2. Cet énoncé est soit le premier énoncé vrai, soit le premier énoncé faux de la liste: Vrai (E)
  3. Cette liste contient au moins énoncés faux consécutifs: Vrai (C)
  4. La différence entre les numéros du dernier énoncé vrai et du premier énoncé vrai est un diviseur de n: Vrai(E)
  5. La somme des numéros des énoncés vrais vaut n: Faux (D)
  6. Ceci n'est pas le dernier énoncé vrai de la liste: Vrai (B)
  7. Le numéro de chaque énoncé vrai est un diviseur de n: Vrai (C)
  8. Exactement n% des énoncés sont vrais: Faux (C)
  9. Le nombre de diviseurs de n strictement compris entre 1 et n est plus grand que la somme des numéros des énoncés vrais: Faux (A)
  10. Cette liste ne contient pas trois énoncés vrais consécutifs: Faux (A)

Ainsi, n est un multiple de 5 selon l'énoncé 4 et un multiple de 2, 3, 4, 6 et 7 selon l'énoncé 7. Les nombres qui ont ces propriétés sont les multiples de 22 3 5 7 = 420. D'autre part, la somme des numéros des énoncés vrais est 2 + 3 + 4 + 6 + 7 = 22, donc puisque l'énoncé 9 est faux, n a au plus 22 + 2 = 24 diviseurs (incluant 1 et n). On compte le nombre de diviseurs d'un nombre n en considérant sa décomposition en facteurs premiers
n = p1m1 p2m2 ... pkmk
et en prenant le produit des exposants plus 1: (m1 + 1) ... (mk + 1). Lorsque n est un multiple de 420 = 22 3 5 7, ce produit vaut au moins 3222 = 24, et atteint cette valeur minimale seulement si n = 420. Par conséquent, n vaut 420.

***************************************

Justifications:

(A) Si l'énoncé 2 est faux, alors ce n'est pas le premier énoncé faux, donc l'énoncé 1 est faux. Par contre, si l'énoncé 2 est vrai, alors c'est le premier énoncé
vrai, donc encore une fois l'énoncé 1 est faux. Par conséquent, l'énoncé 1 est nécessairement faux; il en découle qu'aucun des énoncés 9 et 10 ne peuvent
être vrais.

(B) L'énoncé 6 ne peut être faux, puisqu'alors ce serait le dernier énoncé vrai de la liste, ce qui est une contradiction.

(C) Supposons que l'énoncé 3 soit faux. Alors les énoncés 2 et 8 doivent être vrais pour éviter d'avoir trois énonés faux consécutifs. Mais l'énoncé 8 restreint
considérablement les valeurs possibles pour n: ce doit être un multiple de 10 qui est au moins 40 (puisque la liste contient au moins 4 énoncés vrais en comptant l'énoncé 2 et les trois énoncés vrais consécutifs dont l'existence est assurée par la fallacité de l'énoncé 10) et au plus 60 (puisque la liste comporte déjà 4 énoncés faux).Par conséquent, n n'est pas un multiple de 7, donc l'énoncé 7 doit être faux, ce qui implique que les énoncés 4 et 5 sont vrais puisque la liste doit comporter trois
énoncés vrais consécutifs. Selon l'énoncé 8, n vaut alors 50, mais selon l'énoncé 5, n vaut 2 + 4 + 5 + 6 + 8 = 25, ce qui est une contradiction.

Ainsi, l'énoncé 3 est vrai. L'énoncé 8 doit donc être faux, pour que la liste puisse comporter une suite de trois énoncés faux consécutifs; et l'énoncé 7 doit être vrai, puisque la liste comporte un énoncé vrai àpres l'énoncé 6.

(D) Selon les énoncés 6 et 7, n doit être un multiple de 6 7 = 42. Si l'énoncé (5) était vrai, n vaudrait au plus 2 + 3 + 4 + 5 + 6 + 7 = 27, ce qui est une contradiction. Donc l'énoncé 5 est faux.

(E) Puisque l'énoncé 10 est faux, la liste doit comporter une suite de trois énoncés vrais consécutifs, et la seule possibilité qui reste est la suite 2, 3, 4.

************************************

Commentaires:

  1. Un collègue belge nous a communiqué ce problème, mais il en a égaré la référence, et nous ne savons pas qui est son auteur.
  2. On note que n = 0 serait aussi une solution s'il n'était pas spécifié que n est un entier positif.
  3. LoPesti nous a fait remarquer qu'il nous est nécessaire de spécifier qu'on utilise le tiers exclus, c'est à dire que chaque énoncé qui n'est pas vrai est faux, et chaque énoncé qui n'est pas faux est vrai. Notre liste comporte quelques énoncés tels que 2 et 6 qui sont auto-référents. Nous avons vu en (B) que selon le tiers exclus, l'énoncé 6 est nécessairement vrai puisqu'on arrive à une contradiction en supposant qu'il est faux. Il existe des énoncés beaucoup
    plus problématiques tels que "Cet énoncé est faux'', pour lesquels aucune valeur de vérité n'est satisfaisante. Pour sa part, l'énoncé "Cet énoncé est vrai'', qui
    semble pouvoir prendre les deux valeurs de vérité sans contradiction. Cette situation ressemble beaucoup à celle de l'énoncé 2, dont la valeur de vérité
    a été fixée qu'indirectement, à l'item (E) de notre justification. Or le point de départ de notre justification à l'item (A) utilisait le fait que l'énoncé 2 est
    soit vrai, soit faux, donc il était bien nécessaire d'utiliser le tiers exclus.

Les paradoxes suscités par les énoncés auto-référents ont motivé, au début du vingtième siècle, une ré-examination des fondements des mathématiques.Il n'existe encore aucune solution satisfaisante à certain de ces problèmes.

On note que l'énoncé 2 aurait pu assumer n'importe quelle valeur de vérité

 

Problèmes et solutions précédents
 
Centrale des Maths