L’algorithme du sapeur

Sur les traces du sapeur Camember, Robert March nous invite à étudier les empilements de boulets et la réunion de tels empilements.

Robert March

© APMEP Mars 2022

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

Considérations sur la façon de ranger des boulets de canon

---

La perplexité du sapeur Camember

Le sergent Bitur, ne sachant pas comment occuper ses conscrits, a mis en demeure le sapeur Camember¹ de ranger les boulets de canon stockés dans la cour de la caserne. Ils forment deux tas complets mais le sergent n’en démord pas.

« Sapeur, rangez-moi ces boulets : je ne veux voir qu’un seul tas ! et complet ! »

Avant de s’atteler à la tâche, vu que chaque boulet ne pèse pas moins de \(4\) livres, notre brave sapeur préférerait s’assurer que c’est possible de réunir ces deux tas en un seul. Le premier tas a \(5\) étages et \(5\) boulets en ligne au sommet ; le second \(4\) et \(4\).

« Voyons d’abord ce qu’il en est des pyramides à base carrée, se dit-il : celle à deux étages comporte \(1+2\times 2=5\) boulets ; celle à trois étages \(5+3\times 3=14\) boulets ; celle à quatre étages \(14+4 \times 4=30\) boulets et celle à cinq étages \(30+5\times 5=55\) boulets. Pour la suivante, il faut ajouter \(6\times 6\) à  55, ce qui donne  91 boulets . »

Précisons ici que notre sapeur n’est pas allé plus loin dans sa scolarité que l’école primaire, mais il connaît ses tables ( !) et sait faire des multiplications et des divisions simples (sans virgule, précise-t-il…).

« Je vais maintenant calculer le nombre de boulets de chaque tas. »

Pour le premier, Camember part de la pyramide à 5 étages, de 55 boulets et rajoute sur un côté 4 triangles de \(5+4+3+2+1=15\) boulets.

Il fait ses comptes : \(55+4\times 15=115\) boulets.

Pour le deuxième, il complète la pyramide à 4 étages avec \(3\) fois \(10\) boulets \((1+2+3+4=10)\) pour un total de \(30+3\times 10=60\) boulets. Soit, au total, 175 boulets.

Il s’agit maintenant de réorganiser ces 175 boulets en un seul tas. Il cherche donc s’il existe un tas de 175 boulets à 5 ou 6 étages. La pyramide à 5 étages comptant 55 boulets, il divise \(175-55=120\) par 15, il trouve 8 et ça tombe juste ! Donc, avec 5 étages et 9 boulets au sommet, l’affaire est bouclée ! Pour autant, notre sapeur ne s’arrête pas en si bon chemin. Avec 6 étages, en divisant \(175-91=84\) par 21, il trouve 4 et ça marche aussi ! Il y a donc une deuxième solution à 6 étages et 5 boulets .

Camember, soucieux de s’économiser, après avoir fait le compte du nombre de boulets à soulever pour chaque étage, choisit la première solution :

1^re solution : 16 boulets à monter au 2^e étage ; 12 au 3^e ; 8 au 4^e et 4 au 5^e.

\(16\times 1+12 \times 2+8 \times 3+4 \times 4=80\).

2^e solution : 13 au 2^e ; 11 au 3^e ; 9 au 4^e ; 7 au 5^e et 5 au 6^e : \(13 \times 1+11 \times 2+9\times 3+7\times
4+5\times 5=115\).

L’algorithme du sapeur

Suivons la démarche de Camember.
Soit \(B(n,p)\) le nombre de boulets d’un tas donné :

\(n = \text{nombre d’étages du tas}\) ;

\(p = \text{nombre de boulets alignés au sommet}\).

Calcul de \(B(n,p)\)

Par récurrence sur \(p\)

Calculons d’abord \(B(n,1)\), le nombre de boulets d’une pyramide à \(n\) étages :

\(\begin{aligned}
B(n,1) & = 1^{2}+2^{2}+3^{2}+\cdots+n^{2}=\sum\limits_{k=1}^{n}k^{2}\\
& = \dfrac{n(n+1)(2n+1)}{6}\cdotp
\end{aligned}\)

On passe de \(B(n,1)\) à \(B(n,2)\), de \(B(n,2)\) à \(B(n,3)\), …, de \(B(n,k)\) à \(B(n,k+1)\) en ajoutant \(r\) boulets, avec \[r =1+ 2+ 3+ \cdots + n= \sum\limits_{k=1}^{n}k = \dfrac{n(n+1)}{2}\] Il s’agit donc d’une suite arithmétique de 1er terme \(B(n,1)\) et de raison \(r\).

\(\begin{aligned}
B(n,p) & = \sum\limits_{k=1}^{n}k^{2}+(p-1) \sum\limits_{k=1}^{n}k\\
& = \dfrac{n(n+1)(2n+1)}{6}+(p-1)\dfrac{n(n+1)}{2}\cdotp
\end{aligned}\)

Et finalement : \[B(n,p) = \dfrac{n(n+1)(2n+3p-2)}{6}\cdotp\]

Par récurrence sur \(n\)

On passe de \(B(1,p)\) à \(B(2,p)\) en ajoutant \(2(p+1)\) boulets ; de \(B(2,p)\) à \(B(3,p)\) en ajoutant \(3(p+2)\) boulets ; et de \(B(k-1,p)\) à \(B(k,p)\) en ajoutant \(k(k+p-1)\) boulets.

\(\begin{aligned}
B(n,p) & = \sum\limits_{k=1}^{n}k(k+p-1)\\
& = \sum\limits_{k=1}^{n}\left[k^{2}+(p-1)k\right]\\
& = \sum\limits_{k=1}^{n}k^{2}+(p-1) \sum\limits_{k=1}^{n}k
\end{aligned}\)

On retrouve bien la même formule.

La réunion de deux tas en un seul

Il s’agit de déterminer si un nombre \(N\) est une valeur possible de \(B(n,p)\) et, le cas échéant, les valeurs correspondantes de \(n\) et \(p\). L’équation \(B(n,p)=N\) est une équation à deux inconnues, \(n\) et \(p\), entiers naturels certes, mais du 3e degré en \(n\), ce qui ne facilite pas son étude. On va donc s’en remettre à l’algorithme de notre sapeur, en décidant d’écarter les valeurs trop triviales \(n=1\) et \(n=2\), parce qu’il faut quand même que ça ait l’air d’un tas de boulets !

Algorithme du sapeur

On saisit la valeur de \(N\), ici \(280\).

Algorithme du sapeur

def Sapeur(N) : def CalculB(n) : return n*(n+1)*(2*n+1)//6 # // est le quotient entier n = 3 solution = [N] # initialisation plus simple B = CalculB(n) while ( B < N): D = N-B m = n*(n+1)//2 if D%m==0: p = D//m + 1 # pas besoin de int solution = solution+[[n,p]] # utilisation de la concaténation des # listes plutôt que de la méthode # append # liste [n,p] au lieu du tuple (n,p) # (hors-programme) n = n+1 B = CalculB(n) return solution

À propos d’une observation du sapeur Camember

[+8]Prévoyant, le sapeur dresse un tableau du nombre de boulets composant chaque tas en faisant (le nombre d’étages) de \(3\) à \(10\) et \(p\) de \(1\) à \(10\).

Dans ce tableau, certains nombres n’apparaissent pas, d’autres une ou deux fois. Notre sapeur considère dans le tableau les nombres qui apparaissent deux fois : \(50\), \(70\), \(100\), \(175\), \(196\), \(280\) et \(420\).

Il remarque qu’il s’agit dans chaque cas de deux tas qui n’ont qu’un étage de différence. Serait-ce toujours le cas ? Cherchons les solutions de l’équation : \(B(n,p)=B(n+1,p’)\).

\[\dfrac{n(n+1)(2n+3p-2)}{6}=\dfrac{(n+1)(n+2)\left(2(n+1)+3p’ -2\right)}{6}\]

soit \[\begin{aligned}
n (2n+3p-2)& = (n+ 2)(2n+3p’ )\\
2n^{2}+3pn-2n& =2n^{2}+4n+3p’ n+6p’ \\
3(p-p’ -2)n& = 6p’ \\
p& =\dfrac{2p’ }{n}+p’ +2\end{aligned}\] Pour \(n\) donné, tout \(p’ \) multiple de \(n\) convient (ou multiple de \(\dfrac{n}{2}\) quand \(n\) est pair). On a donc une de solutions pour tout \(n\), certaines pouvant être quadruples, quintuples, etc.

Par exemple :

\(280\)	\((4,26)\), \((5,16)\), \((6,10)\), \((7,6)\) ;
\({1120}\)	\((4,110)\), \((5,72)\), \((6,50)\), \((7,36)\), \((14,2)\).

Pour tout observateur curieux, les conjectures ne manquent pas.

Ces considérations n’étaient certes pas à la portée du sapeur Camember mais elles auraient certainement pu distraire de son idée fixe le Cosinus, polytechnicien de son état, autre création du facétieux et brillant scientifique .

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

Robert March est maître de conférences retraité et a enseigné en sciences et techniques pour l’architecture.

---

1. Les facéties du sapeur Camember est l’œuvre de Georges Colomb, alias Christophe, aussi facétieux qu’éminent scientifique (1856–1945). On le verra ici, et quoi qu’on ait pu en dire, Camember n’a rien d’un simple d’esprit. On doit également à cet auteur L’idée fixe du savant Cosinus.↩

---