Solution au problème de novembre 2012

Le problème:

Soit $w$, un mot (séquence) de $n$ lettres choisies (avec répétitions permises) parmi celles du mot "chikwangue''. Démontrer qu'il existe une bijection de $\{ \mbox{c, h, i, k, w, a, n, g, u, e} \}$ dans $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ telle qu'en remplaçant chaque lettre par le chiffre correspondant, on obtient un multiple de 3. Par exemple, avec la correspondance $\mbox{c}=0, \mbox{h}=1, \mbox{i}=2, \ldots, \mbox{e}=9$, "uniguaneaukiwi'' donne 86278569583242, un multiple de 3. Donner un exemple d'un tel mot pour lequel aucune bijection de $\{ \mbox{c, h, i, k, w, a, n, g, u, e} \}$ dans $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ ne permet d'obtenir un multiple de 7 en substituant chaque lettre par le chiffre correspondant. (Note: Le chikwangue est un mets traditionnel du bassin du fleuve Congo, aussi apprécié par les amateurs de scrabble. L'iguane au kiwi, c'est juste pour rire.)

Nous avons reçu les solutions correctes de

Solution à la partie (a)
Voici la solution de Bruno Tisserand:

"On s’appuie sur le critère de divisibilité par 3 pour un nombre en base 10 : un nombre est divisible par 3 si la somme de ses chiffres est divisible par 3 (comme $10 \equiv 1 [3]$, on a $10n \equiv 1 n [3]$ c'est-à-dire $10n ≡ n [3]$ ce qui donne directement qu’un nombre est congru à la somme de ses chiffres en base 10, et donc le critère de divisibilité par 3)

Construction d’une bijection

On s’aperçoit assez facilement que le nombre d’occurrence d’une lettre dans le mot $w$ peut se réduire sans que cela change le critère de divisibilité : il suffit de prendre le reste $r$ modulo 3 du nombre d’occurrences et de ne considérer que $r$ occurrences de cette lettre pour garder le même critère de divisibilité. Les restes possibles modulo 3 pour le nombre d’occurrences sont $\{ 0, 1, 2 \}$. Les lettres à 0 occurrence modulo 3 n’ont aucun « poids » dans le critère de divisibilité. On commence donc par s’occuper des lettres dont l’occurrence est 1 ou 2 modulo 3. L’idée est de regrouper 2 par 2 les lettres d’occurrence identique (modulo 3) et de leur affecter dans cet ordre les couples $(1, 8)$, $(2, 7)$, $(3, 6)$, $(4,5)$, $(0, 9)$ ce qui annule 2 par 2 leur « poids » modulo 3 dans le mot de par le choix des couples dont la somme fait 9 et du fait du regroupement des lettres d’occurrence identique (modulo 3). Il peut rester une lettre isolée pour chacune des 2 catégories. Dans ce cas, le couple (0,9) est libre (car on a 10 lettres au maximum) et on peut affecter à la lettre isolée restante la valeur 0 ou affecter aux deux lettres isolées restantes les valeurs 0, et 9, ce qui annule de facto leur poids modulo 3 dans le mot. Les lettres à 0 occurrence modulo 3 peuvent ensuite se voir affecter n’importe lequel des chiffres restants pour compléter la bijection. Par construction le nombre généré est divisible par 3

Exemple :

uniguaneaukiwi

occurrence de {c, h, i, k, w, a, n, g, u, e} = {0, 0, 3, 1, 1, 2, 2, 1, 3, 1} équivalent à {0, 0, 0, 1, 1, 2, 2, 1, 0, 1} modulo 3

on pose $k=1$, $w=8$, $g=2$, $e=7$ puis $a=3$, $n=6$,(pas de lettre isolée dans cet exemple) puis $c=4$, $h=5$, $i=0$, $u=9$ pour compléter la bijection.

uniguaneaukiwi=96029367391080

9+6+0+2+9+3+6+7+3+9+1+0+8+0 = 63 donc 96029367391080 est divisible par 3.''

Solution à la partie (b).
Voici la solution Benoît Humbert:

"Le mot suivant convient :

$$w = acaaaaahaaaaaiaaaaakaaaaawaaaaaaaaaaanaaaaagaaaaauaaaaaeaaaaa. $$

Pour une meilleure lisibilité, écrivons ce mot en allant à la ligne toutes les six lettres :

$$ w = \begin{array}{cccccc} & & & & & a\\c & a & a & a & a & a \\h & a & a & a & a & a\\i & a & a & a & a & a\\k & a & a & a & a & a\\w & a & a & a & a & a\\a & a & a & a & a & a\\n & a & a & a & a & a\\g & a & a & a & a & a\\u & a & a & a & a & a\\e & a & a & a & a & a\end{array}$$

Montrons qu'aucune bijection ne transforme ce mot en un nombre multiple de 7 :

Modulo 7, on a les congruences suivantes :

\begin{eqnarray*} 1 & = & 1\\ 10 & = & 3\\ 100 & = & 2\\ 1000 & = & -1\\ 10000 & = & -3\\ 100000 & = & -2\end{eqnarray*}.

1000000, et toutes ses puissances, sont congrus à 1.

On a donc :

\begin{eqnarray*} w & = & a \times (10 \times (1+3+2-1-3) +1) -2 (c+h+i+k+w+a+n+g+u+e)\\ & = & 21a - 2 (c+h+i+k+w+a+n+g+u+e) \\& = & -2 (0+1+2+3+4+5+6+7+8+9)\\& = & -90 \\& = & 1\end{eqnarray*}.

Quelle que soit la bijection utilisée, elle transforme $w$ en un nombre congru à 1 modulo 7, donc non multiple de 7.''

Commentaires. La partie (a) est le problème 1859 du journal Crux Mathematicorum (20:6, juin 1994, pages 168-170), proposé par N. Kildonan. La solution offerte mentionnait notre partie (b) comme défi supplémentaire. On retrouve ensuite cette partie (b) comme problème Macalester de la semaine #1093 (en février 2008). On trouve plus de commentaires sur leur page http://mathforum.org/wagon/about.html et sur notre page anglaise.