E5903. Le coût minimal Imprimer
E5. Enigmes logiques

calculator_edit.png  

Cent cartes numérotées de 1 à 100 sont alignées dans cet ordre sur une même rangée.
La permutation de deux cartes adjacentes coute un euro tandis que la permutation de deux cartes avec exactement k cartes placées entre elles est gratuite.
Déterminer le coût minimal du classement des cartes dans l’ordre inverse de 100 à 1 avec  a) k = 3 et b) k = 4.

 Solution



pdfPierre Henri Palmade,pdfJean-Louis Legrand,pdfPierre Leteurtre,pdfDiophante,pdfThérèse Eveilleau,pdfMaxime Cuenot et pdfJean Nicot ont tous prouvé que le classement des cartes dans l'ordre inverse pouvait être réalisé en un nombre fini de permutations avec des coûts variables selon les réponses. Le coût minimal est de 50 € pour k = 3 et de 61 € pour k = 4.

Zig dispose d’une calculette de marque déposée @Méphisto dont le clavier comporte trois touches qui permettent d’obtenir à partir d’un entier quelconque n strictement positif affiché à l’écran :
 1) φ(n), fonction d’Euler, le nombre d’entiers qui sont strictement inférieurs à l’entier n et sont premiers avec lui.
2) σ(n) la somme des diviseurs de l’entier n, y compris 1 et lui-même.
3) τ(n) le nombre des diviseurs de l’entier n, y compris 1 et lui-même.
Q₁ Démontrer qu’il existe une infinité d’entiers n strictement positifs tels que l’entier n égalise son sigma (σ) diminué de son phi (φ) et de son tau(τ).
Q₂ Démontrer qu’il existe au moins un entier n strictement positif tel que son double égalise son sigma (σ) augmenté de son phi(φ) et diminué de son tau(τ).
Q₃ Démontrer qu’il existe une infinité de paires d’entiers strictement positifs (m,n) tels que le rapport des deux entiers est l’inverse du rapport de leur sigma (σ).
Q₄ Soit un entier k ≥ 1. Démontrer que l’équation σ(n) = n + k a un nombre fini de solutions.
Application numérique : déterminer le plus grand entier n₀ tel que σ(n₀) = n₀ + 2021. Démontrer qu’il existe un entier n₁ > n₀ tel que φ(n₁) = n₁ – 2021