Solutions

Énoncé n° 307 (François DUC, 84-Orange)

On veut pouvoir peser avec une balance Roberval n’importe quel objet de masse
entière, inférieure ou égale à M grammes, en disposant uniquement de n poids dont
la somme des masses ne dépasse pas M. Exprimer en fonction de M la plus petite
valeur possible de n, et indiquer les masses des poids correspondants.

SOLUTION
J’ai reçu des solutions de Richard BECZKOWSKI (71-Chalon sur Saône), René
BENOIT (91-Palaiseau), Christine FENOGLIO (69-Lyon), J.C. LAUGIER (17-
Rochefort), René MANZONI (76-Le Havre), Annie PERROT (75-Paris), Pierre
SAMUEL (92-Bourg la Reine) et André STEF (54-Nancy), mais tout le monde n’a
pas vu que chaque poids peut être mis soit sur le plateau de droite, soit sur le plateau
de gauche de la balance. De sorte qu’avec n poids, de masses $a_1, a_2, \ldots, a_n,$ on peut
peser les objets de masse :

|$\epsilon_{1}a_{1} + \epsilon_{2}a_{2} + \ldots+ \epsilon_{n}a_{n} $|, avec $\epsilon_{k} = 1$ si on met le k-ième
poids sur le plateau de droite, $\epsilon_{k} = -1$ si l’on met le k-ième poids sur le plateau de gauche et $\epsilon_{k} = 0$ si l’on n’utilise pas le k-ième poids. Si la somme est positive, il
faudra mettre l’objet à peser sur le plateau de gauche, sinon il faudra le mettre sur le
plateau de droite.

Il est clair qu’on obtient ainsi au plus $3^{n}$ sommes distinctes, dont 0, et que si la
somme s est obtenue, la somme −s l’est également. De sorte qu’avec n poids, on peut
peser au plus $(3^{n} -1)$/2 masses distinctes strictement positives.

Si donc
$\frac{3^{n} -1}{2}< M \leq \frac{3^{n+1}-1}{2 }$, il faudra au minimum (n + 1) poids. Pour peser toutes
les masses entre 1 et $\frac{3^{n} -1}{2}$, il suffit de prendre des poids de masse $1, 3, 9, \ldots, 3^{n-1} $ : cela se prouve par récurrence sur n.

Si tous les entiers entre $-\frac{3^{n} -1}{2}$ et

$\frac{3^{n} -1}{2}$

peuvent s’écrire

$\epsilon_{1}+ \epsilon_{2}x3 +\ldots+ \epsilon_{n}x3^{n-1} $

(ce qui est manifestement vrai pour
n = 1), tout entier k entre $-\frac{3^{n+1}-1}{2}$ et $\frac{3^{n+1}-1}{2} $ peut s’écrire

$\epsilon_{1}+ \epsilon_{2}x3 +\ldots+ \epsilon_{n}x3^{n-1} +\epsilon_{n+1}x3^{n} $,

avec $\epsilon_{n+1} = +1$ si $k > \frac{3^{n}-1}{2}$,

$\epsilon_{n+1} = -1$ si $k < -\frac{3^{n}-1}{2}$,

$\epsilon_{n+1} = 0$ sinon.

Pour peser toutes les masses entre 1 et M, il suffit de remplacer la dernière masse
$3^n $ par :

$m = M -\frac{3^{n}-1}{2}$.

On n’a d’ailleurs pas le choix : un poids plus léger ne
permettrait pas d’atteindre la masse M, un poids plus lourd ne respecterait pas
l’hypothèse de l’énoncé que la somme des masses ne dépasse pas M.

Le
raisonnement ci-dessus s’applique en remplaçant $3^n$ par m, et permet de conclure que
le nombre cherché est : $1 + E(log_{3}(2M + 1))$.

Un problème voisin, classique, consiste à trouver parmi 3n pièces, dont une seule
est plus légère, laquelle est plus légère, avec n pesées sur une balance Roberval. Si
une seule de M pièces est différente des autres, mais soit plus légère soit plus lourde,
comment faut-il s’y prendre pour la déterminer avec le minimum de pesées ?