DS 1 — Nombres narcissiques et inversions de permutations

Informatique tronc commun (MPSI), année scolaire 2021-2022 — durée totale 2h.

Consignes

Tout document et dispositif électronique interdit.

I. Nombres narcissiques

On ne considère dans cette partie que des valeurs entières dans \(\N\).

On s'efforcera de ne pas se répéter en utilisant les fonctions précédemment définies.

Question 1. Montrer que si \(n, k \in \N\), le \(k\)-ième (en partant de la droite) chiffre dans l'écriture décimale de \(n\) est donné par \(c_k = (n / 10^{k}) \mod 10\) où l'on rappelle que \(a \mod b\) est le reste dans la division euclidienne de \(a\) par \(b\).

Corrigé

Erreur d'énoncé : il manque une partie entière, il faut lire \(c_k = \lfloor n / 10^{k} \rfloor \mod 10\).

On sait qu'on peut écrire \(n = \sum_{i=0}^p c_i 10^{i}\) en écriture décimale à \(p+1\) chiffres où \(n < 10^{p+1}\).

On a donc \(\lfloor n / 10^{k} \rfloor = c_k + 10 \sum_{i=k+1}^{p} c_i 10^{i-k-1} \equiv c_k ~[10]\).

Question 2. En déduire une fonction chiffre telle que l'appel à chiffre(n,k) renvoie la valeur de \(c_k\) (on utilisera les opérations usuelles de division euclidienne présentes dans Python, et ainsi, on ne reprogrammera pas la division euclidienne).

Corrigé

Cette fonction est la traduction directe de la formule précédente :

def chiffre(n, k):
    return (n // (10**k)) % 10

Question 3. Montrer que si \(n \in \N\), il existe \(N \in \N\) tel que \(\forall k \ge N, c_k = 0\) (i.e. que la suite des chiffres est presque nulle).

Corrigé

Il s'agit ici de montrer la finitude de l'écriture d'un entier.

On sait que la suite \((10^k)\) tend vers \(+\infty\) donc il existe un \(N\) à partir duquel \(10^k > n\), et alors \(\lfloor n / 10^k \rfloor = 0\) donc \(c_k = 0\).

Question 4. En déduire une fonction degre telle que l'appel à degre(n) où \(n \neq 0\) renvoie le plus grand \(k\) tel que \(c_k \neq 0\).

Corrigé

Attention, il ne faut pas chercher le plus petit \(k\) pour lequel \(c_k = 0\) et prendre le rang d'avant, car il peut très bien y avoir des \(0\) au milieu de l'écriture du nombre. Par exemple \(103\) est de degré \(2\) et non \(0\).

Il faut donc procéder par division de \(n\) et trouver le plus grand \(k\) tel que le quotient de \(n\) par \(10^k\) soit non nul.

On calcule les quotients de \(n\) en divisant progressivement par \(10\) à chaque étape :

def degre(n):
    d = 0
    while n >= 10:
        d = d + 1
        n = n // 10
    return d

Question 5. En déduire une fonction chiffre_dominant telle que l'appel à chiffre_dominant(n) où \(n \neq 0\) renvoie le chiffre non nul situé le plus à gauche dans l'écriture décimale de \(n\).

Corrigé

Par définition il suffit donc de renvoyer \(c_{\deg n}\) avec le degré obtenu à l'étape précédente :

def chiffre_dominant(n):
    return chiffre(n, degre(n))

Question 6. Écrire une fonction somme_chiffres telle que l'appel à somme_chiffres(n) calcule la somme des chiffres dans l'écriture décimale de \(n\).

Corrigé

Dans cette question et les suivantes, on va se servir de degre pour fournir la plage d'indices à prendre en compte pour obtenir les chiffres significatifs de \(n\).

def somme_chiffres(n):
    s = 0
    for k in range(degre(n)+1):
        s = s + chiffre(n, k)
    return s

Question 7. On rappelle que l'on peut créer un tableau \(t\) de \(m\) cases contenant la valeur \(0\) à l'aide de l'instruction

t = [ 0 ] * m

Écrire une fonction chiffres telle que l'appel à chiffres(n) renvoie le tableau des chiffres dans l'écriture décimale de \(n\), telle qu'à l'indice \(i\) on ait le chiffre \(c_i\) suivant la numérotation de la question 1.

Corrigé

La structure de la réponse à cette question est proche de la question précédente, une fois le tableau initialisé comme dans l'énoncé (attention il contient \(\deg(n)+1\) cases car on va de \(0\) à \(\deg(n)\) inclus !) on le remplit dans une boucle :

def chiffres(n):
    t = [ 0 ] * (degre(n)+1)
    for k in range(degre(n)+1):
        t[k] = chiffre(n, k)
    return t

Question 8. On dit qu'un entier \(n\) est narcissique si son écriture décimale comporte \(p\) chiffres et que \(\sum_{i=1}^p c_i^p = n\) où \(c_i\) est le \(i\)-ème chiffre de \(n\).

Déterminer une fonction est_narcissique telle que est_narcissique(n) renvoie True si \(n\) est narcissique et False sinon.

On rappelle encore une fois qu'il est demandé de réutiliser les fonctions précédentes (notamment ici degre et chiffre…).

Corrigé

Ici il faut faire attention car \(p = \deg(n) + 1\). On fait donc un calcul de la somme comme précédemment mais en rajoutant la puissance \(p\) et ensuite on renvoie le test : \(n\) est-il égal à cette somme ?

def est_narcissique(n):
    s = 0
    p = degre(n)+1
    for k in range(p):
        s = s + chiffre(n, k)**p
    return s == n

Attention ce n'est pas la peine d'écrire ce genre de choses :

if (s == n) == True:
    return True
else:
    return False

le code précédent return s == n renvoie directement la même valeur !

Les nombres narcissiques non nuls inférieurs à \(10\,000\) sont \(1, \dots, 9, 153, 370, 371, 407, 1634, 8208\) et \(9474\).

II. Inversions de permutations

Sujet d'après CCINP 2019.

Pour tout \(n \in \N^*\), une permutation de taille \(n\) est une bijection de l'ensemble \(\range{0}{n-1} = \{ 0, 1, \dots, n-1 \}\) dans lui-même. Dans la suite, l'ensemble des permutations de taille \(n\) est noté \(\mathfrak{S}_n\). Étant donné une permutation \(\sigma\) de taille \(n\), on la représente sous la forme \(\sigma_0 \sigma_1 \dots \sigma_{n-1}\) où :

\[ \forall i \in \{ 0, 1, \dots, n-1 \}, \sigma_i = \sigma(i) \]

Par exemple, \(\sigma = 1032\) représente la permutation envoyant \(0\) sur \(1\), \(1\) sur \(0\), \(2\) sur \(3\) et \(3\) sur \(2\).

Soit \(\sigma = \sigma_0 \dots \sigma_{n-1}\) une permutation de taille \(n\). On dit que \((i,j) \in \{0, 1, \dots, n-1\}^2\) est une inversion de \(\sigma\) si \(\sigma_i > \sigma_j\) et \(i < j\). On note \(inv(\sigma)\) le nombre d'inversions de \(\sigma\). Tout d'abord, on relie ce nombre avec un algorithme de tri : le tri à bulles. Puis, on s'intéresse à la table d'inversions d'une permutation, un objet qui caractérise une permutation.

Dans la suite, une permutation de taille \(n\) est représentée en Python par un tableau sans répétition contenant tous les entiers compris entre 0 et \(n-1\). Par exemple, le tableau [1, 0, 3, 2] représente la permutation \(\sigma = 1032\).

Si \(A\) est un ensemble fini, \(Card(A)\) désigne le cardinal de l'ensemble \(A\). Pour tout entier \(n \ge 1\), on pose \(E_n = \prod_{k=1}^n \{0, 1, \dots, n-k\}\). Par exemple, on a \(E_3 = \{0,1,2\} \times \{0,1\}\times \{0\}\).

Tri et inversions

Question 9. Déterminer l'ensemble des inversions de la permutation \(\sigma = 140253\).

Corrigé

On a les inversions : \((0, 2), (1,2), (1,3), (1,5), (4, 5)\) qui correspondent respectivement aux comparaisons \(1 > 0, 4 > 0, 4 > 2, 4 > 3\) et \(5 > 3\).

On rappelle l'algorithme du tri à bulles :

• Entrée : un tableau d'entiers \(L\)
• Pour \(i\) allant de (taille de \(L\)) \(-1\) à \(1\) (bornes incluses) faire
  • Pour \(j\) allant de (taille de \(L\)) \(-1\) à (taille de \(L\)) \(-i\) (bornes incluses) faire
    • Si \(L[j] < L[j-1]\) alors
      • Échanger \(L[j]\) et \(L[j-1]\)

On rappelle également que for i in reversed(range(a,b)) permet de parcourir de \(b-1\) à \(a\) en descendant.

Question 10. Écrire une fonction tri_bulle qui prend en argument un tableau d'entiers \(L\) et qui trie ce tableau à l'aide du tri à bulles. À l'issue de la fonction, le tableau est trié.

Corrigé

def tri_bulle(L):
    for i in reversed(range(1, len(L))):
        for j in reversed(range(len(L)-i, len(L))):
            if L[j] < L[j-1]:
                L[j], L[j-1] = L[j-1], L[j]

Dans la suite, on admet que l'algorithme du tri à bulles est bien un algorithme de tri.

Question 11. Montrer que si on effectue exactement un échange dans un tableau lors du tri à bulles, le nouveau tableau a exactement une inversion en moins.

Corrigé

L'algorithme échange \(L[j]\) et \(L[j-1]\) lorsque \(L[j]<L[j-1]\) : cela supprime une inversion. Montrons qu'on n'en a pas ainsi créé d'autre. La position relative des \(L[i]\) pour \(i<j-1\) par rapport aux valeurs initialement en \(j-1\) et \(j\) ne change pas, donc le nombre d'inversions non plus. De même pour les \(L[i]\) avec \(i>j\).

Question 12. En déduire une fonction Python nombre_inversions qui prend en argument un tableau L correspondant à une permutation et renvoyant le nombre d'inversions de celle-ci. Cette fonction sera une légère modification du tri à bulles.

Corrigé

def nombre_inversions(L):
    total = 0
    for i in reversed(range(1, len(L))):
        for j in reversed(range(len(L)-i, len(L))):
            if L[j] < L[j-1]:
                L[j], L[j-1] = L[j-1], L[j]
                total = total + 1
    return total

Table d'inversions d'une permutation

Définition (table d'inversions)

Soit \(\sigma\) une permutation de taille \(n \ge 1\). La table d'inversions de \(\sigma\) est le \(n\)-uplet \((\alpha_0, \dots, \alpha_{n-1})\) tel que :

\[ \forall i \in \{0,\dots, n-1\}, \alpha_i = Card\left( \enscomp{j \in \{i+1, \dots, n-1\}}{\sigma_j < \sigma_i} \right) \]

Elle est notée \(Tab_\sigma\). De plus, pour tout \(i \in \{0,\dots, n-1\}\), \(Tab_\sigma[i]\) désigne \(\alpha_i\).

Pour tout \(n \ge 1\), on désigne par \(Tab : \mathfrak{S}_n \rightarrow E_n\) l'application qui associe à une permutation de taille \(n\) sa table d'inversions.

Question 13. Déterminer la table d'inversions de la permutation \(\sigma = 140253\).

Corrigé

Il s'agit de \([1, 3, 0, 0, 1, 0]\).

Question 14. Montrer que pour toute permutation \(\sigma\) de taille \(n \ge 1\), \(Tab_\sigma\) est bien un élément de \(E_n\).

Corrigé

Soit \(\sigma\) une permutation de taille \(n\geq 1\). Avec les notations de l'énoncé, pour tout \(i\in \range{0}{n-1}\),

\[ \alpha_i = Card \enscomp{j\in \range{i+1}{n-1}}{\sigma_j<\sigma_i} \leq Card\ \range{i+1}{n-1} = n-i-1 \]

donc \(\alpha_{i}\in\{0,\dots, n-i-1\}\), ce qui, avec le décalage d'indice, correspond au terme général du produit cartésien définissant \(E_n\).

Question 15. Soit \(\sigma\) une permutation de taille \(n \ge 1\). Montrer que \(\sigma_0 = Tab_\sigma[0]\).

Corrigé

On a \(\alpha_0= Card \enscomp{j\in \range{1}{n-1}}{\sigma_j<\sigma_0}\). Mais puisque \(\sigma_0\not<\sigma_0\), c'est aussi \(Card \enscomp{j\in \range{0}{n-1}}{\sigma_j<\sigma_0}\). Puisque \(\sigma\) est une permutation, on a donc \(\alpha_0= Card \enscomp{j\in \range{0}{n-1}}{j<\sigma_0}\), ce qui vaut \(\sigma_0\).

Question 16. Montrer que pour tout entier \(n \ge 1\), l'application \(Tab\) est bijective.

Corrigé

Compte tenu de l'égalité des cardinaux (\(Card(\mathfrak{S}_n) = n! = Card(E_n)\)), il suffit de montrer l'injectivité.

Soit \(n\geq1\) et soit \(\sigma\) et \(\sigma'\) deux permutations de taille \(n\) qui ont la même table \(\alpha\). On va montrer que \(\sigma^{-1}=\sigma'^{-1}\).

En effet, l'indice du zéro est nécessairement \(\min\enscomp{k\in \range{0}{n-1}}{\alpha_k=0}\) : c'est forcément un tel \(k\) (ce qui assure qu'il existe de tels \(k\)), et si \(\sigma_k=0\) et \(k'<k\) alors \(\alpha_{k'}>0\) à cause du zéro situé à droite de \(k'\).

Notons donc \(k_0=\sigma^{-1}(0)=\sigma'^{-1}(0)\). S'il existe \(k\in \range{0}{k_0-1}\) tel que \(\alpha_k=1\) alors la plus petite de ces positions est \(\sigma^{-1}(1)=\sigma'^{-1}(1)\) ; sinon cette position est \(\min\enscomp{k\in \range{k_0+1}{n-1}}{\alpha_k=0}\).

On note \(k_1=\sigma^{-1}(1)=\sigma'^{-1}(1)\). En traitant comme ci-dessus les différentes possibilités, on montre de même que \(\sigma^{-1}(2)=\sigma'^{-1}(2)\). De proche en proche on détermine \(\sigma^{-1}=\sigma'^{-1}\) puis \(\sigma=\sigma'\).

Question 17. Écrire une fonction Python permutation_vers_table qui prend en argument une permutation représentée par le tableau L et qui renvoie la table d'inversions correspondante.

Corrigé

def permutation_vers_table(L):
    n = len(L)
    res = [0] * n
    for i in range(0, n):
        compte = 0
        for j in range(i+1, n):
            if L[j] < L[i]:
                compte = compte + 1
        res[i] = compte
    return res

Question 18. Écrire une fonction Python table_vers_permutation qui prend en argument un tableau L qui correspond à une table d'inversions et qui renvoie la permutation qui lui est associée.

Corrigé

def table_vers_permutation(L):
    n = len(L)
    sigma = [0] * n
    deja_mis = [False] * n
    for i in range(0, n):
        k = 0
        compte = 0
        while deja_mis[k] or compte < L[i]:
            if not deja_mis[k]:
                compte = compte + 1
            k = k + 1
        sigma[i] = k
        deja_mis[k] = True
    return sigma