Pesées - Trouver un/des sacs de pièces fausses

Pour fixer les idées, trouver des sacs de fausses pièces (de 9g ou 11g) parmi 10 sacs de pièces sensées faire 10g.
La méthode générale consiste à prendre a₁ pièces du premier sac, a₂ pièces du 2^ème sac ... a_n pièces du n^ème sac.
Le poids théorique est la somme des a_i. L'écart d avec cette valeur donne la réponse.
Il faut que tous les a_i soient différents et on peut donc imposer a₁<a₂<a₃...<a_n
Selon les conditions du problème, il faut assurer que toutes les combinaisons de sacs faux donnent des combinaisons de a_i différentes. Etudions le cas simplissime :

trouver 1 sac parmi n

Les "combinaisons" sont ici simplement le choix d'un sac, c'est à dire d'un a_i. Les a_i étant simplement différents, il suffit de choisir a_i=i-1, c'est à dire 0 pièce du 1^er sac, 1 du 2^ème, 2 du 3^ème... et n-1 du n^ème.
Remarquons que ceci est vrai pour un énoncé qui affirme qu'un des sacs est faux. Si les sacs peuvent être tous bons, la valeur d=0 est réservée à ce cas et a_i=i qui est la solution généralement admise (1 pièce du 1^er sac, 2 du 2^ème...n du dernier). Passons maintenant aux choses sérieuses.

trouver 2 sacs parmi n

Si l'énoncé affirme que deux sacs sont faux, les combinaisons sont les sommes de deux a_i. Toutes ces sommes doivent être différentes. On peut fixer a₁=0 et a₂=1 (minimum). Alors a₁+a₂=1 et il faut choisir a₃+a₁>1, la plus petite valeur est a₃=2. Les nouvelles sommes avec ce sac sont 2+0 et 2+1 et a₄+a₁>3, soit a₄=4
En continuant ainsi de proche en proche à choisir le plus petit a_i donnant avec les autres des sommes différentes de toutes celles déjà trouvées, on obtient la suite :

0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73, 94, 127, 151, 181, 211, 257, 315, 373, 412 ...

Si l'énoncé est "1 ou deux sacs faux", alors les combinaisons sont les sommes de deux a_i et les a_i eux même. Le minimum est a₁=1 car a₁+a_i doit être différent de a_i, et on obtient en fait la même suite décalée d'un cran.
Si l'énoncé dit enfin "0,1 ou 2 sacs faux", cela ne change rien puisque la valeur 0 (tous les sacs bons) n'est plus utilisée.
Notez que cette méthode ne garantit pas que cette suite est la meilleure (a_i et/ou somme des a_i minimale).

A cause du caractère erratique de la suite, le décodage consiste essentiellement à chercher la différence dans sa table d'addition.

7					19
4				11	16
2			6	9	14
1		3	5	8	13
0	1	2	4	7	12
	1	2	4	7	12

Des suites plus simples existent si on ne cherche pas la meilleure. Outre qu'elles sont aisément calculables, elles ont une propriété intéressante pour le décodage : l'un des sacs faux est repéré par le plus grand a_i≤d.

• a_i=2^i-1: 1, 2, 4, 8, 16...
• a_i=a_i-1+a_i-2+1 : (0), 1, 2, 4, 7, 12, 20, 33...
• Enfin si on est sûr qu'il y a deux sacs faux, la suite de Fibonnacci : a_i=a_i-1+a_i-2 : 1, 2, 3, 5, 8, 13...

trouver 1 sac léger et 1 sac lourd

C'est à dire un sac de pièces de 9g et un sac de pièces de 11g. Les combinaisons sont les différences des a_i. En partant de a₁=0 et a₂=1, on choisit a_i le plus petit donnant des différences pas encore trouvées, on obtient la suite :

0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147, 181, 203, 251, 289, 360, 400, 474 ...

S'il peut y avoir un seul sac faux, la valeur 0 est exclue et on prend la suite décalée d'un cran. Ceci détecte aussi le cas où tous les sacs sont bons. Pour décoder on utilise la table de soustraction de la suite.

	1	3	7	12	20
0	1	3	7	12	20
-1		2	6	11	19
-3			4	9	17
-7				5	13
-12					8

Là encore a_i=2^i-1 fonctionne aussi car on montre aisément que les différences de deux puissances de 2 sont toutes différentes. Mais ce n'est pas la solution la plus économique.

deux sacs quelconques

(un sac plus lourd l'autre plus léger ou les deux plus lourds, ou les deux plus légers).
La suite a_i=2^i-1 ne marche plus : par exemple une différence de 3=2+1=4-1 ne permettrait pas de savoir si les sacs 1 et 2 sont plus lourds ou bien si le sac 1 est plus léger et le sac 3 plus lourd.
En cherchant comme précédemment de proche en proche les plus petits a_i ayant des sommes et différences avec les a_i précédents différentes de toutes celles déjà trouvées, on obtient la suite :

1, 2, 6, 12, 21, 37, 58, 84, 112, 129, 173, 213, 266, 307, 373, 446, 513, 589, 639, 829 ...

Le décodage s'effectue à partir des tables d'addition et de soustraction de la suite.
Par exemples, une différence de 14=12+2 indique les sacs 2 et 4 trop lourds,
une différence de 15=21-6 indique le sac 5 trop lourd et le sac 3 trop léger etc...

21					58
12				33	49
6			18	27	43
2		8	14	23	39
1	3	7	13	22	38
	2	6	12	21	37
-1	1	5	11	20	36
-2		4	10	19	35
-6			6	15	31
-12				9	25
-21					16

trouver tous les sacs

C'est à dire qu'on ne sait pas combien de sacs de fausses pièces il y a

1. Les fausses pièces sont toutes identiques
   En choisissant a_i=2^i-1, le problème est résolu : c'est la représentation en binaire de la différence.
   Cette solution est optimale car donnant toutes les posibilités, sans trous.
   Pour décoder : Les bits à 1 de la différence donnent les rangs des sacs de fausses pièces. Par exemple si la différence est 25=11001₂, les sacs de fausses pièces sont les sacs 1, 4 et 5.
   Nota : a₁₀=2⁹=512. Les sacs doivent avoir suffisament de pièces. De plus la balance doit accepter 1+2+4+...+512=1023 pièces soit plus de 10kg avec une précision meilleure que 1g.

2. Des sacs de pièces plus légères et des sacs de pièces plus lourdes
   Les pièces d'un même sac sont toutefois identiques, mais certains sacs peuvent contenir des pièces de 9g et d'autres des pièces de 11g.
   La suite a_i=3^i-1 convient. C'est à dire :

   1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049...

   Donc des gros sacs de pièces et une super balance capable de peser (3¹⁰-1)/2×11g soit plus de 300kg à moins de 1 gramme près !
   La différence est représentée en "ternaire" c'est à dire en base 3 avec les chiffres 0 -1 et +1.
   La relation 2x3ⁱ=3ⁱ⁺¹-3ⁱ permet de convertir une représentation en base 3 en représentation ternaire ou vice-versa.
   Soit la représentation de la différence en base 3 : r₀3⁰+r₁3¹+r₂3²+...r_n-13^n-1
   Par exemple une différence de 70g s'écrit en base 3 "ordinaire" : (2121)₃=2×27+1×9+2×3+1
   Et en ternaire : 70=(2121)₃=(+0--+)_±3=1-3-9+81 Un nombre négatif se convertit en ternaire en changeant le signe de tous les chiffres : -70=(-0++-)_±3
   Les +1 de la représentation indiquent les sacs de pièces trop lourdes et les -1 les sacs de pièces trop légères. Par exemple si le poids est de 70g trop lourd, les sacs 1 et 5 sont trop lourds et les sacs 2 et 3 trop légers.
   Cette solution est optimale puisqu'on obtient sans trous tous les nombres entre -(3ⁿ-1)/2 et (3ⁿ-1)/2.