Retour

Source de general_chinois.tex

Fichier TeX
\exo{Pas bête ce général chinois}

Pour dénombrer un de ses bataillons, un général chinois a l'idée suivante~: tout d'abord, il sait
que ce bataillons compte moins de~$1000$ soldats. Ensuite il exige de ses troupes de se mettre
par paquets de sept et remarque que seuls deux soldats n'ont pas trouvé place dans aucun groupe.
Il prend note de ce nombre deux. Il réitère le même expérience en exigeant que les soldats se
rangent par paquets de onze puis treize. Dans le premier cas il note que seulement trois soldats
n'ont pas trouvé place dans aucun groupe et dans le second seul un hurluberlu n'a pas trouvé à
s'insérer nul part. Ces informations lui suffisent pour dénombrer son bataillon.

\q Quel est donc le secret de cet ingénieux général chinois~?

{\bfseries Indication~:} les premiers~$7$, $11$ et~$13$ n'ont évidemment pas été choisis au hasard.
De même l'ordre des exercices de cette feuille ne relève pas d'un tirage aléatoire...

\ifwithcorrection \correction

Notons~$x$ le nombre de soldats composant le bataillon de ce général. Par hypothèse, ce nombre
satisfait le système de congruences suivant~:
$$
\begin{cases} x \equiv 2 \pmod{7} \\ x \equiv 3 \pmod{11} \\ x \equiv 1 \pmod{13} \end{cases}
$$
Ce système admet des solutions,~$7$,~$11$ et~$13$ étant premiers entre eux deux-à-deux. Pour
déterminer ces solutions, on sait qu'il convient de déterminer les coefficients de Bezout liant
les entiers~$7 \times 11$, $7 \times 13$ et~$11 \times 13$. Comme~:
$$
6 (7 \times 11) - 5 (7 \times 13) = 7
\qquad \text{et} \qquad 41 \times 7 - 2 (11 \times 13) = 1
$$
(les coefficients de Bezout étant déterminés gr’ce à l'algorithme d'Euclide étendu) on obtient~:
$$
41 \times \left[ 6 (7 \times 11) - 5 (7 \times 13) \right] -2(11 \times 13) = 1
\qquad \Rightarrow \qquad
246 (7 \times 11) - 205 (7 \times 13) - 2 (11 \times 13) = 1
$$
Posons~$x_{13} = 246 (7 \times 11)$, $x_{11} = - 205 (7 \times 13)$
et~$x_7 = - 2 (11 \times 13)$ alors l'entier~:
$$
2 x_7 + 3 x_{11} + x_{13} = -37595
$$
est solution du système de congruences. Comme~$1001 = 7 \times 11 \times 13$, l'ensemble~$S$ des
solutions est donné par~:
$$
S = \{-37595 + 1001q, \; q \in \ZZ\}
$$
Parmi ces entiers, seul un est positif et inférieur ou égal à~$1000$, c'est~$443$ (obtenu
avec~$q = 38$). Par conséquent le bataillon compte~$443$ soldats.
\fi