Codage – Bac S Nouvelle Calédonie 2013
Bac S Nouvelle Calédonie 2013
On note $E$ l'ensemble des vingt-sept nombres entiers compris entre $0$ et $26$.
On note $A$ l'ensemble dont les éléments sont les vingt-six lettres de l'alphabet et un séparateur entre deux mots, noté « * », considéré comme un caractère.
Pour coder les éléments de $A$, on procède de la façon suivante :
Premièrement : on associe à chacune des lettres de l'alphabet, rangées par ordre alphabétique, un nombre entier naturel compris entre $0$ et $25$, rangés par ordre croissant. On a donc $a \mapsto 0$, $b \mapsto 1$, … $z \mapsto 25$.
On associe au séparateur « * » le nombre $26$.
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| p | q | r | s | t | u | v | w | x | y | z | * |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
On dit que $a$ a pour rang $0$, $b$ a pour rang $1$, …, $z$ a pour rang $25$ et le séparateur « * » a pour rang $26$.
Deuxièmement : à chaque élément $x$ de $E$, l'application $g$ associe le reste de la division euclidienne de $4x+3$ par $27$.
On remarquera que pour tout $x$ de $E$, $g(x)$ appartient à $E$.
Troisièmement : le caractère initial est alors remplacé par le caractère de rang $g(x)$.
Exemple : $s \mapsto 18$, $g(18) = 21$ et $21 \mapsto v$. Donc la lettre $s$ est remplacée lors du codage par la lettre $v$.
- Trouver tous les entiers $x$ de $E$ tels que $g(x) = x$, c'est-à-dire invariants par $g$. En déduire les caractères invariants dans ce codage.
- Démontrer que, pour tout entier naturel $x$ appartenant à $E$ et tout entier naturel $y$ appartenant à $E$, si $y \equiv 4x+3 \ \left[27\right]$ alors $x \equiv 7y+6 \ \left[27\right]$. En déduire que deux caractères distincts sont codés par deux caractères distincts.
- Proposer une méthode de décodage.
- Décoder le mot « vfv ».
Corrigé
$g(x) = x$ si et seulement si $0 \leqslant x \leqslant 26$ et :
$ 4x+3 \equiv x \ \left[27\right] $
Cette congruence est vérifiée si et seulement s'il existe un entier relatif $k$ tel que :
$ 4x+3 = x + 27k $
$ 3x = 27k - 3 $
$ x = 9k - 1 $
Pour $k \leqslant 0$, les valeurs de $x$ obtenues sont strictement négatives ; pour $k > 3$, elles sont strictement supérieures à $26$.
On obtient donc trois solutions comprises entre $0$ et $26$ :
- $x = 8$ (pour $k = 1$)
- $x = 17$ (pour $k = 2$)
- $x = 26$ (pour $k = 3$)
Par conséquent, les caractères invariants dans ce codage sont $i$, $r$ et *.
Si $y \equiv 4x+3 \ \left[27\right]$ alors :
$ 7y \equiv 7(4x+3) \ \left[27\right] $
$ 7y \equiv 28x + 21 \ \left[27\right] $
Comme $28 \equiv 1 \ \left[27\right]$ et $21 \equiv -6 \ \left[27\right]$, on a alors :
$ 7y \equiv x - 6 \ \left[27\right] $
donc $ x \equiv 7y + 6 \ \left[27\right] $.
Soient deux entiers naturels $x$ et $x'$, compris entre $0$ et $26$, ayant la même image $y$ par $g$. Alors $g(x) = y$ et $g(x') = y$.
Par conséquent, $x \equiv 7y + 6 \ \left[27\right]$ et $x' \equiv 7y + 6 \ \left[27\right]$.
Donc, comme $x$ et $x'$ sont compris entre $0$ et $26$, ils sont tous deux le reste de la division euclidienne de $7y+6$ par $27$. L'unicité du reste entraîne que $x = x'$.
Par conséquent, si deux caractères sont codés de façon identique, c'est qu'ils sont identiques. Autrement dit, deux caractères distincts sont codés par deux caractères distincts.
La formule $x \equiv 7y + 6 \ \left[27\right]$ permet de décoder un caractère. Il suffit de procéder de la façon suivante :
- 1ʳᵉ étape : à chaque lettre on associe son rang $y$.
- 2ᵉ étape : à chaque valeur de $y$, l'application $h$ associe le reste de la division euclidienne de $7y+6$ par $27$.
- 3ᵉ étape : le caractère initial est alors remplacé par le caractère de rang $h(y)$ trouvé à la seconde étape.
On utilise la méthode décrite précédemment :
- $v \mapsto y = 21$ ; $h(21)$ est le reste de la division de $7 \times 21 + 6 = 153$ par $27$. Or $153 = 27 \times 5 + 18$ donc $h(21) = 18$ et $18 \mapsto s$.
- $f \mapsto y = 5$ ; $h(5)$ est le reste de la division de $7 \times 5 + 6 = 41$ par $27$. Or $41 = 27 \times 1 + 14$ donc $h(5) = 14$ et $14 \mapsto o$.
Le mot « vfv » se décode donc en « sos ».