Nous allons maintenant donner une méthode par codage des pièces que nous
généraliserons ensuite au cas de pièces de poids inconnu.
Numérotons les pièces de -(3n - 1)/2 à +(3n - 1)/2, dans le système
"ternaire", système à base 3 avec les "chiffres" +1, -1 et 0, notés plus
simplement + - 0.
Par exemple la pièce numéro 11 = 9+3-1 = ++-, la pièce numéro -11 = -9-3+1 = --+.
Alors chaque chiffre représente une pesée. Un + indique que la pièce est dans
le plateau de gauche, un - qu'elle est dans le plateau de droite et un 0 qu'elle est sur la
table.
Par exemple la pièce 6 = +-0 est dans le plateau de gauche à la première pesée, dans celui de
droite à la deuxième pesée et reste sur la table à la dernière pesée. La pièce codée 000
n'est jamais pesée. Ceci donne un plan de pesées indépendant de la pièce fausse.
Notons maintenant + le résultat d'une pesée où le plateau de gauche est plus lourd (>),
- une pesée où le plateau de gauche est plus léger (<) et 0 si elle est en équilibre (=).
Alors le résultat cumulé des trois pesées donne l'opposé du numéro de la pièce (l'opposé
car la pièce fausse est plus légère...)
Par exemple un résultat >=< ou +0- = +8 donne la pièce numéro -8 fausse.
Passons maintenant à plus coriace :
Avec p pièces il y a 2p cas (plus lourde ou plus légère), et avec n pesées on détermine
3n possibilités :
p ≤ (3n - 1)/2, car
[(3n)/2] = (3n - 1)/2.
Une pesée concerne q pièces dans chaque plateau et il reste p - 2q pièces sur la table.
En cas d'équilibre la pièce fausse est parmi les p-2q pièces laisées de coté.
Ceci correspond à 2(p - 2q) cas (plus lourde ou plus légère) et doit être résolu par les
n - 1 autres pesées
Donc : (p - 2q) ≤ (3n-1 - 1)/2 ou encore :
q ≥ (2p - 3n-1 + 1)/4
En cas de déséquilibre il y a 2q cas, soit :
q ≤ (3n-1 - 1)/2 et en résumé :
(2p - 3n-1 + 1)/4 ≤ q ≤ (3n-1 - 1)/2
Cette double inégalité n'est possible que si
(2p - 3n-1 + 1)/4 ≤ (3n-1 - 1)/2
et finalement :
| p ≤ (3n - 3)/2 |
Par exemple avec 3 pesées on trouve une pièce parmi 12. Une pesée concerne 4 pièces dans chaque plateau.
Pour appliquer la méthode par codage, les pièces seront codées en ternaire entre 1 et
(3n - 3)/2
Il faut aussi affecter un signe à chaque pièce pour avoir autant de + que de - à chaque
pesée.
Par exemple avec 3 pesées, en tâtonnant un peu on trouve un codage possible :
+1, +2, -3, +4, +5, +6, -7, -8, +9, -10, -11, +12
soit en appelant A à L les 12 pièces, les pesées :
|
- 1ère pesée : EFIL et GHJK
- 2ème pesée : BDGL et CEFK - 3ème pesée : ADHK et BEGJ |
| = = = impossible : elles ont toutes le même poids | |||
| = = > : A+ | = > < : B+ | = > = : C- | = > > : D+ |
| = = < : A- | = < > : B- | = < = : C+ | = < < : D- |
| > < < : E+ | > < = : F+ | > < > : G- | > = < : H- |
| < > > : E- | < > = : F- | < > < : G+ | < = > : H+ |
| > = = : I+ | > = > : J- | > > < : K- | > > = : L+ |
| < = = : I- | < = < : J+ | < < > : K+ | < < = : L- |
Soit M la 13ème pièce, et gardons la dans la poche. On peut dire que si le résultat de pesée est 000, c'est que toutes les pièces pesées ont le même poids et donc que c'est M qui est fausse, sans pouvoir dire si elle est plus lourde ou plus légère.
Une autre astuce est d'emprunter une pièce bonne ¥ à un ami pour
compléter les pesées avec les pièces :
M = 13 = +++ et ¥ = --- , soit :
- 1ère pesée : EFILM et GHJK¥
- 2ème pesée : BDGLM et CEFK¥
- 3ème pesée : ADHKM et BEGJ¥
Et à complèter le tableau de décodage avec
| > > > : M+ | < < < : M- |
Le résultat = = = indique que toutes les pièces sont bonnes, si on fait confiance à la pièce ¥.
3 pièces : +1+2-3 (2 pesées)
4 pièces : +1+2+4-7 (3 pesées)
5 pièces : -1+3+4+6-12
6 pièces : +1+2-3+4+5-9
7 pièces : +2+5+6-7-8-11+13
8 pièces : +2+4+5+6-7-8+9-11
9 pièces : +4+5+6-7-8+9-10-11+12
10 pièces : -1+2-3+4+6-8+9-10-11+12
11 pièces : +2-3+4+5+6-7-8+9-10-11+13
12 pièces : +1+2-3+4+5+6-7-8+9-10-11+12
Ou si vous avez la flemme de calculer :
- 1ère pesée : OPRTUXYcdfgjm avec NQSVWZabehikl
- 2ème pesée : EFILMNQSVfgjm avec GHJKOPRTUhikl
- 3ème pesée : BDGLMNTUWcdhm avec CEFKOPVXYefgl
- 4ème pesée : ADHKMNPQWYZil avec BEGJSTVbcefhk
La paresse m'empêche d'ailleurs de donner (chercher) les solutions avec 13 à 38 pièces ainsi que les cas n>4 (avec n = 5, p = 120 !)
| 000 éliminé | ||
| 00+ éliminé (0+) | 00- (-1) | |
| 0+- éliminé (0+) | 0-+ (-2) | |
| 0+0 éliminé (0+) | 0-0 (-3) | |
| 0++ éliminé (0+) | 0-- (-4) | |
| +-- éliminé (+-) | -++ (-5) | |
| +-0 éliminé (+-) | -+0 (-6) | |
| +-+ éliminé (+-) | -+- (-7) | |
| +0- (+8) | -0+ éliminé (-0) | |
| +00 (+9) | -00 éliminé (-0) | |
| +0+ (+10 | -0- éliminé (-0) | |
| ++- éliminé (+-) | --+ (-11) | |
| ++0 (+12) | --0 éliminé (-0) | |
| +++ éliminé | --- éliminé |
Une pesée concerne 2q pièces et p - 2q restent sur la table. Ce qui fait que, en cas
d'équilibre il reste q² cas où les deux pièces identiques sont chacune dans un plateau
et (p - 2q)(p - 2q - 1)/2 cas où les deux pièces sont sur la table.
Ces q² + (p - 2q)(p - 2q - 1)/2 cas doivent être distinguables
par les n - 1 autres pesées.
soit q² + (p - 2q)(p - 2q - 1)/2 ≤ 3n-1,
inéquation du second degré en q :
f(q) = 6q² - 2(2p - 1)q + p(p - 1) - 2×3n-1 ≤ 0.
Le discriminant (réduit) est
Δ' = (2p - 1)² + 4×3n - 6p(p - 1))
Avec n = 3 et p = 7 Δ' = 25
Les racines sont (2p - 1 ± √Δ')/6 soit dans notre
exemple 4/3 et 3, q doit être entre les racines et q = 2 ou 3.
En cas de déséquilibre de la pesée, les pièces fausses sont toutes deux dans le plateau
le plus léger : q(q - 1)/2 cas, ou bien l'une dans le plateau le plus léger et l'autre sur
la table : q(p - 2q) cas.
Soit q(q - 1)/2 + q(p - 2q) ≤ 3n-1 ou encore :
g(q) = 3q² - (2p - 1)q + 2×3n-1 ≥ 0.
Le discriminant est (2p - 1)² - 8×3n Dans notre exemple il vaut -47 et
g(q) > 0 quelque soit q.
A suivre ....