Énigme des 12 pièces et une balance
L'énigme se présente ainsi.
Parmi 12 pièces, il y a 1 qui est fausse du fait qu'elle a un poids légèrement différent (entre 0.7 et 1.3 du poids régulier des 11 autres par exemple).
On dispose d'une balance à deux plateaux ([large]R[/large]oberval) parfaite.
En combien de pesées au minimum peut-on à coup sûr isoler cette fausse pièce ?
Justifier la réponse, et proposer une formule générale donnant le nombre de pesées pour X pièces, ou inversement, le nombre maximal de pièces solvables pour N pesées.
[Gilles Personne de Roberval (1602-1625) prend toujours une majuscule. AD]
Parmi 12 pièces, il y a 1 qui est fausse du fait qu'elle a un poids légèrement différent (entre 0.7 et 1.3 du poids régulier des 11 autres par exemple).
On dispose d'une balance à deux plateaux ([large]R[/large]oberval) parfaite.
En combien de pesées au minimum peut-on à coup sûr isoler cette fausse pièce ?
Justifier la réponse, et proposer une formule générale donnant le nombre de pesées pour X pièces, ou inversement, le nombre maximal de pièces solvables pour N pesées.
[Gilles Personne de Roberval (1602-1625) prend toujours une majuscule. AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour 12 j’ai deux solutions avec trois pesées :
5 vs 5
2 vs 2
Ou
4 vs 4
Yves, as-tu bien pris en compte qu'on ne sait pas si la pièce frelatée est plus lourde ou moins lourde ?
Une solution générale (pas relue depuis 2016)
Merci les deux formules semblent OK et effectivement j'avais les mêmes résultats sans vos fonctions N = f(n) pour l'intruse, et dire si elle est plus lourde ou légère (mais ce n'était pas la question), par la logique (et non les mathématiques), en me basant sur l'entropie de l'information ce qui m'avait fait viré de la Faculté il y a 30 ans...
Donc je suis intéressé par votre raisonnement pour arriver à votre fonction...
Ma démo était :
a. initialement l'ensemble des suspects contenait N boules/pièces...
b. la balance était E
Et le raisonnement était basé sur la quantité d'information que pouvait fournir la balance à chaque pesé,
suite à un E -> E,D (D pour déséquilibre Gauche ou Droite puisqu'on sait qu'elle a un poids différent, pas plus lourde ou plus légère)
et suite à un D -> D, I, E (I pour inversion, désolé, je ne sais pas faire D barre)
Donc, en déployant l'arbre issu de E initial, on 2 possibilités après 1ere pesé, 5 après un 2e, 13 après un 3e, ...etc, mais on va s'arrêter là,
car logiquement peu importe comment faire les pesés, on sait que si c'est fait de manière optimale, on peut diviser/partitioner en 13, l'ensemble des suspects, N=12, et N/13 < 1 => c'est possible en 3 pesés, sans savoir si c'est plus lourde ou plus légère, ce qui n'était pas demandé, ni comment les faire, ce qui n'était pas non plus demandé !!!
Et le comment se retrouve facilement, car en "relisant" l'arbre de la feuille vers la racine, on voit la capacité de partinionenement que chaque pesé doit satisfaire pour rester optimale => à la 1ere pesé, la sous-branche E cumule 5 feuilles, la sous-branche D cumule 8 feuilles, donc il faut se débrouiller pour qu'en cas de D, l'ensemble des suspects ne soient plus que 8, or si D l'ensemble des suspects est donné par les boules/pièces sur la balance => il faut qu'il y ait 8 sur la balance à la 1ere pesé => 4+4, et 5 restants hors de la balance...
L'inversion n'a de sens qu'après un D, et voudrait dire que le suspect a changé de plateau, donc il suffit de partager, de partitionner en retirant des boules en prévision de E à la pesée suivante, changer de plateaux en prévision de I, et laisser le nombre approprié en cas de D, encore le même déséquilibre...
Ce que je n'arrive pas (car n'étant pas mathématicien du tout), c'est le lien avec vos formules N = f(n)
Il me semble que toutes les justifications sont dans le document. Le codage que j'ai pris et qui me semble plus naturel est G, E, D pour Gauche, Etal ou Droite, ce qui vous donne immédiatement $3^n$ feuilles.
Je ne vois pas ce que vous voulez dire par 5 vs 5 ou 2 vs 2. En tout état de cause, si on doit chercher parmi un nombre inférieur au max, les pesées sont assez "évidentes" (par contre je n'ai pas réfléchi à comment les générer), la première pesée permettant de déterminer un certain nombre de boules normales
Une pièce est $B$ si elle est bonne (i.e.: non fausse); la pièce fausse est $F$; les pièces sont numérotées de $1$ à $12$; $F\in l$ si elle est légère, $\in L$ si elle est Lourde.
La première pesée est $1234 $ contre $5678$
Trois cas:
Cas 1) $1234=5678]\Leftrightarrow F\in \{9,10,11,12\}$
alors, la deuxième pesée est $9, 10, 11$ contre $ BBB$
1.1) $9, 10, 11 = BBB\Leftrightarrow F=12$
1.2) $9, 10, 11 < BBB\Leftrightarrow F \in \{ 9, 10, 11 \} \wedge l $
alors, la troisième pesée est $9$ contre $10$
1.2.1) $9=10\Leftrightarrow F=11$
1.2.2)$9<10\Leftrightarrow F=9$
(car $F \in l$)
1.2.3)$9>10\Leftrightarrow F=10$
(car $F \in l$)
1.3)$9, 10, 11 > BBB$
On passe du cas 1.2) au cas 1.3) par symétrie.
Cas 2) $1234<5678\Leftrightarrow F\in (\{1,2,3,4\} \wedge l )\vee (\{5,6,7,8\} \wedge L)$
alors, la deuxième pesée est $5BBB$ contre $1678$
2.1) $5BBB=1678\Leftrightarrow F\in \{2,3,4\} \wedge l$.
alors, la troisième pesée est $2$ contre $3$
2.1.1) $2=3\Leftrightarrow F=4$
2.1.2) $2<3\Leftrightarrow F=2$
2.1.3) $2>3\Leftrightarrow F=3$
2.2)$5BBB<1678\Leftrightarrow F\in \{6,7,8\} \wedge L$.
alors, la troisième pesée est $6$ contre $7$
2.2.1) $6=7\Leftrightarrow F=8$
2.2.2) $6<7\Leftrightarrow F=7$
2.2.3) $6>7\Leftrightarrow F=6$
2.3)$5BBB>1678\Leftrightarrow F\in \{1,5\}$.
alors, la troisième pesée est $1$ contre $B$
2.3.1) $1=B\Leftrightarrow F=5$
2.3.2) $1\neq B\Leftrightarrow F=1$
Cas 3)$1234>5678\Leftrightarrow F\in (\{1,2,3,4\} \wedge L)\vee (\{5,6,7,8\} \wedge l)$.
On passe du cas 2) au cas 3) par symétrie.
aux très probables coquilles près!
Cordialement
Paul
Merci de la précision je comprends mieux (3^n-1)/2 mais sauf qu'à n=4, je ne vois pas comment vous pouvez résoudre avec 40 boules/pièces,
car pour moi, c'est max 34 boules/pièce en 4 pesées, au regard de l'entropie d'infos obtenues au fur et à mesure des pesés... En fait comme j'ai évoqué, je pense avoir la solution pour n pesées mais je ne sais pas calculé f(n) donnant le max, je suis obligé d'énumérer la somme de deux suites...
Et comme évoqué, j'ai l'algorithme qui peut générer les pesés pour n'importe quel nombre de boules/pièces, mais je suis obligé de développer mon arbre jusqu'à ce que le nombre de "feuilles" soit supérieur au nombre de boules/pièces, et par récursion terminale, les pesés sont calculées à l'envers, les dernières pesées puis enfin la première pesée!!!
Quant à 5vs5 ou 2vs2 ou 4vs4 c'était en rapport à la réponse de Yves dont j'ai supposé qu'il parlait de sa 1ere pesée...
Cordialement,
Polo
Pour n = 4 le maximum c'est 39 boules/pièces, les 4 pesées sont données en bas de la page 4.
E(n), le nombre de cas issus d'un Equilibre après n pesées,
D(n), le nombre de cas issus d'un Déséquilibre après n pesées,
P(n) = E(n)+D(n)
E(n) = E(n-1)+D(n-1), avec une pesée de plus, chaque cas d'Equilibre va induire un cas Equilibre (et un cas Déséquilibre), et chaque cas de Déséquilibre va induire un cas d'Equilibre (et deux cas de Déséquilibre, la même et son inversion)
D(n) = E(n-1)+2*D(n-1)
mais après n'étant pas matheux, j'avoue mes limites...
avec les conditions initiales...
E(0) = 1, la balance étant parfaite donc à l'équilibre avant la 1ere pesée...
D(0) = 0, pour les mêmes raisons, étant parfaite, elle ne peut être en déséquilibre
E(1) = 1
D(1) = 1
P(1) = E(1)+D(1) = 1+1 = 2 sauf qu'il est impossible de faire une pesé avec une seule boule/pièce
P(2) = E(2)+D(2) = (E(1)+D(1))+(E(1)+2*D(1)) = (1+1)+(1+2*1) = 5
P(3) = E(3)+D(3) = (E(2)+D(2))+(E(2)+2*D(2)) = (2+3)+(2+2*3) = 13
P(4) = E(4)+D(4) = (E(3)+D(3))+(E(3)+2*D(3)) = (5+8)+(5+2*8) = 34 (!?)
car la génération des pesées peut se baser sur une des deux prédicats suivantes exclusivement ou inclusivement...
- Soit le fait qu'en cas d'Equilibre, ce sont les boules/pièces qui n'étaient pas sur la balance, dont si par récursion terminale on connait de nombre de feuilles E, on peut s'arranger pour garder hors de la balance un sous ensemble de suspects
- Soit le fait qu'en cas de Déséquilibre, ce sont les boules/pièces qui étaient sur la balance qui deviennent des suspects, donc faire monter ou garder sur la balance, un sous-ensemble de suspects, tout en exploitant les inversions en faisant changer de plateau, un autre sous ensemble de suspects
On partage ou réduire ainsi le nombre de suspects au fur et à mesure...
Donc pour 13 boules/pièces, donc en 3 pesés, et la 1ere serait :
Soit 8 sur la balance et le reste (13-8=5) sur le côté
Soit 5 sur le côté et le reste sur la balance (13-5=8) = ce qui revient au même
8/2 est faisable => 4.vs.4 pour la 1ère
Donc pour 34 boules/pièces donc en 4 pesés, et la 1ere serait :
Soit 21 sur la balance et le reste (34-21=13) sur le côté
Soit 13 sur le côté et le reste sur la balance (13-5=8) = ce qui revient au même
21/2 n'est pas faisable => il faut réduire à 33 sauf si on est sûr d'un loyal pour faire monter 21+ce loyal pour faire 22/2, 11.vs.11 pour la 1ère, sinon à 33, c'est 10.vs.10 avec 13 hors de la balance, en cas d'Equilibre, on revient au pb initial, et en cas de déséquilibre on n'a plus que 20 réductibles par 21
C'est pour cela que (3^n-1)/2 ou (3^n-3)/2 me paraît "trop simple"...je sais qu'on est au pays de Fermat, donc il a fallu 300 ans sur une intuition
Cordialement,
Paul & Mickey
;-)
39 => on met 13 hors de la balance, 26 sur la balance, 13.vs.13, en cas E on revient à 13 en 3 pesés, et en G ou D et la connaissance du fait que celle qu'on cherche est plus lourde ou plus légère permet de sélectionner le plateau du haut ou du bas, pour revenir à 13 en 3 pesés...
Mais du fait du poids différent et en cas de Désequilibre => vous met dans l'impossibilité de déterminer lesquels des 13 sur les 26 sur la balance, restent suspectes
(et je comprends mieux votre codage G-E-D...)
En 2 pesées il peut se produire 9 évènements, or avec 5 boules, cela vous donnes 10 possibilités, c'est donc impossible.
Par contre, pour 39 boules vous avez le détail dans mon document, il suffit de vérifier.
C'est pour ça que j'ai dû resté avec E, Etale, Equilibre et D, Déséquilibre (D barre inversion)
Avec en plus le fait que si le cumule des événements D est impaire, il est impossible de faire la 1ere pesé (sauf si vous disposez d'un étalon supplémentaire dès le départ ce qui n'est pas l'énoncé)
GG, GE, GD, EG, EE, ED, DG, DE, DD
C'est vous qui annoncez 5 boules en 2 pesées, moi je dis 3 boules.
b. La balance ne change d'état que si on a déposé, retiré, ou changé le suspect recherché dans les manipulations après une pesé
en cas d'événement (E)quilibre, la suspecte fait partie des boules/pièces qui ont été retirées ou restées hors de la balance;
en cas d'événement (D)éséquilibre (suite à un E), la suspecte fait partie des boules/pièces qui ont été déposées sur la balance;
en cas d'événement (!D) inversion du déséquilibre (suite à un D), la suspecte fait partie des boules/pièces qui ont été changés de plateau;
c. Donc il n'y a aucune autre information que (E) ou (D) après un (E), et (!D) n'a de sens qu'après un (D), donc il n'y a pas toujours 3 événements équiprobables à chaque pesé...
d. Et il faut pouvoir faire la 1ere pesé donc le cumul du nombre des événements (D) en feuille en développant un tel arbre, doit être paire pour la branche (D) sinon il faut réduire de 1 la capacité pour rendre paire => P(2) = 5 mais comme D(2) = 3 alors il faut retirer 1
P(n) = E(n) + D(n) - ( D(n) mod 2 )
Ce qui rend encore plus compliqué P(n) en fct(n)
...qui n'est pas la façon la plus facile d'y répondre!!!
B-)
Je suis surpris d'apprendre que cette question pouvait être un motif de licenciement d'une faculté il y a 30 ans.
Heureusement que ce genre de chose ne pourrait plus avoir cours à l'heure actuelle.
À bientôt.
[Édit : Merci de m'avoir expliqué qu'il n'était pas question d'une perte de poste mais d'un règlement de compte sur un étudiant.
Du coup, cela reste possible.]
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
EG et ED ne sont pas 2 séquences différentes (désolé je m'exprime peut-être plutôt mal)
Par contre,effectivement j'ai commencé par dire 5 du fait du cumul de 2 E et 3 D au terme de 2 pesés, mais en discutant dans ce forum, je me suis aperçu que si le cumul des D est impaire alors on ne peut faire la 1ere pesé, donc il faut l'arranger, l'arrondir à quantité paire inférieure donc
P(n)=E(n)+D(n)-(D(n) mod 2), soit 4
Soit a,b,c,d, 4 "enquêtes" à faire sur 4 suspects, donc il faut les désigner, les nommer ou les étiqueter...
On fait monter D(n) sur la balance, D(n)-(D(n) mod 2), soit 2, a et b de chaque côté, et le reste c,d, hors de la balance
1ere pesé : a _ b
1.en cas de D => on fait remplacer b par c (sachant c et d sont déjà sont hors de cause)
2ème pesé : a _ c
1.1.en cas de D => c'est a
1.2.en cas de E => c'est b
2.en cas de E => on fait remplacer b par c (sachant que a et b déjà sont hors de cause)
2ème pesé : a _ c
2.1.en cas de D => c'est c
2.2.en cas de E => c'est d (sans savoir si plus lourd ou plus léger, mais ce n'est pas demandé)
Donc en 2 pesés, il est possible de retrouver 4 boules/pièces (et pas 3, car vous pouvez "réduire" en 5 mais à cause du fait qu'il faut un nombre paire à la 1ère pesé
=> soit on retire 1 inconnue, et revoir nos ambitions à 4 boules/pièces (ou 1 certitude ce qui revient au même pour la 1ère pesé, d'où la précaution dans l'énoncé, "(((légèrement))) différent" obligeant à avoir un nombre égal de boules/pièces de chaque côté)
=> soit on doit faire une pesé de plus
Donc à 39 en 4 pesés, je suis curieux de voir comment? (puisque que vous semblez vouloir démontrer par le "comment")
Tandis que moi, je me rectifie avec mon modulo 2 de 34 à 33 = 13+21-(21 mod 2)
Soit a,b,c,d,e,f,g,h,i,j,k,l,m,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T
On fait monter D(n) sur la balance, D(n)-(D(n) mod 2), soit 20, 10 de chaque côté, et le reste abcdefghijklm hors de la balance
1ère pesé: ABCDOPQRST _ EFGHIJKLMN
1.si D alors on se retrouve ABCDMNOPIJEFGHQRSTUV comme suspects en 3 pesés mais ayant 13 étalons et un D donc pouvant exploiter les inversions !D (entropie de l'info a évolué)
car le prochain coup, il s'agit de réduire cette ensemble 20 en fonction de 3 événements possibles, D, même équilibre, E, retour à l'équilibre, !D, inversion de l'équilibre. Donc on va manipuler de sorte qu'en cas de D, ce sera celles qu'on n'a pas bougées, E, ce sera celles qu'on a retiré, et !D, ce sera celles qu'on a bougées.
=> il faut retirer 4, IJKL par exemple, et faire bouger 8 des 16 restantes de plateau en compensant avec abcdefghijklm,
2ème pesé : ABCDMNabcd _ EFGHOPQRST
1.1.si D alors on se retrouve avec ABCDEFGH comme suspects en 2 pesés restantes,
=> il suffit de retirer 2, DE par exemple, et faire bouger 3 des 6 restantes de plateau en compensant avec abcdefghijklm
3ème pesé : ABCFGH _ abcdef
1.1.1.si D alors on se retrouve avec ABC comme suspects en 1 pesé restante
=> il suffit de retirer 1, B par exemple, et faire bouger 1 des 2 restantes de plateau en compensant avec abcdefghijklm
4ème pesé : A _ C
1.1.1.1.si D alors on se retrouve avec A comme seul suspect
1.1.1.2.si E alors on se retrouve avec B comme seul suspect
1.1.1.3.si !D alors on se retrouve avec C comme seul suspect (il a bougé lors de cette dernière pesé)
1.1.2.si E alors on se retrouve avec DE comme suspects en 1 pesé restante
=> il suffit de faire monter sur la balance 1, D par exemple en compensant avec abcdefghijklm
4ème pesé : D _ a
1.1.2.1.si D alors on se retrouve avec D comme seul suspect
1.1.2.2.si E alors on se retrouve avec E comme seul suspect
1.1.3.si !D alors on se retrouve avec FGH comme suspects en 1 pesé restante, symétrie de 1.1.1
on peut donc transposer avec ABC en 1.1.1 ci-dessus
=> il suffit de retirer 1, H par exemple, et faire bouger 1 des 2 restantes de plateau en compensant avec abcdefghijklm
4ème pesé : F _ G
1.1.1.1.si D alors on se retrouve avec F comme seul suspect
1.1.1.2.si E alors on se retrouve avec H comme seul suspect
1.1.1.3.si !D alors on se retrouve avec G comme seul suspect
1.2.si E alors on se retrouve avec IJKL comme suspects en 2 pesés (voir ci-dessus la suite en 4 en 2 coups)
3ème pesé : I _ J
1.2.1.si D alors on a IJ comme suspects en 1 pesé
4ème pesé : I _ a
1.2.1.1.si D alors on se retrouve avec I comme seul suspect
1.2.1.2.si E alors on se retrouve avec J comme seul suspect
1.2.2.si E alors on a KL comme suspects en 1 pesé
4ème pesé : K _ a
1.2.1.1.si D alors on se retrouve avec K comme seul suspect
1.2.1.2.si E alors on se retrouve avec L comme seul suspect
1.3.si !D alors on se retrouve avec MNOPQRST comme suspects en 2 pesés restantes et comme c'est l'une inversion, cela devient sysmétrique
on peut transposer avec ABCDEFGH en 1.1 ci-dessus
3ème pesé : Oabcd _ MNRST
1.3.1.si D alors on se retrouve avec MNO comme suspects en 1 pesé restante
=> il suffit de retirer 1, N par exemple, et faire bouger 1 des 2 restantes de plateau en compensant avec abcdefghijklm
4ème pesé : ab _ MO
1.3.1.1.si D alors on se retrouve avec M comme seul suspect
1.3.1.2.si E alors on se retrouve avec N comme seul suspect
1.3.1.3.si !D alors on se retrouve avec O comme seul suspect (il a bougé lors de cette dernière pesé)
1.3.2.si E alors on se retrouve avec PQ comme suspects en 1 pesé restante
=> il suffit de faire monter sur la balance 1, P par exemple en compensant avec abcdefghijklm
4ème pesé : P _ a
1.1.2.1.si D alors on se retrouve avec P comme seul suspect
1.1.2.2.si E alors on se retrouve avec Q comme seul suspect
1.1.3.si !D alors on se retrouve avec RST comme suspects en 1 pesé restante, symétrie de 1.1.1
=> il suffit de retirer 1, S par exemple, et faire bouger 1 des 2 restantes de plateau en compensant avec abcdefghijklm
4ème pesé : R _ T
1.1.1.1.si D alors on se retrouve avec R comme seul suspect
1.1.1.2.si E alors on se retrouve avec S comme seul suspect
1.1.1.3.si !D alors on se retrouve avec T comme seul suspect
2.si E alors on se trouve avec abcdefghijklm, soit 13 en 3 pesés, et une balance à E
=> voir les différentes réponses donnant les différentes variantes
Et je ne vois pas comment vous pouvez y parvenir avec 39 en 4...
-Dés que j'ai une pesée non équilibrée, je marque les pièces pesées: un + si elle est parmi le tas le plus lourd, un - si elle est parmi le tas le plus léger. Or je sais détecter ensuite en $k$ pesées la pièce différente parmi $3^k$ pièces marquées (ce qui est bien sûr optimal), par ce que j'appelle algorithme des pièces marquées:
à chaque pesée, je divise mon tas en trois tas égaux de sorte qu'il y ait autant de pièces marquées + dans les tas 1 et 2 (c'est toujours possible). En pesant le tas 1 avec le tas 2 je vais forcément diviser par trois les pièces suspectes: si il y a équilibre, je ne garde que le tas 3, et si par ex le tas 1 est plus lourd, je ne garde que les + du tas 1 et les - du tas 2. Idem dans l'autre sens si le tas 2 est plus lourd.
(remarque: la variation classique où on sait à l'avance si la pièce différente est plus lourde est un cas particulier de ce sous problème, car ça revient à dire que toutes les pièces sont marquées +)
Maintenant l'algo général est le suivant, avec disons n pesées:
-A la première pesée, je veux peser $3^{n-1}$ pièces. Mais j'ai besoin d'un nombre pair donc j'en pèse seulement $3^{n-1}-1$, divisées en deux tas égaux. Si il n'y a pas équilibre, je marque les pièces pesées puis utilise l'algorithme des pièces marquées avec mes $n-1$ pesées restantes pour trouver la pièce
-Si il y a équilibre, j'élimine toutes les pièces pesées et avec les restantes je refais presque la même chose que la première pesée, à une nuance prés: je veux peser $3^{n-2}$ pièces, qui est encore un nombre impair, mais cette fois on a pas besoin d'enlever une pièce (ce serait pas optimal), à la place je rajoute une des pièces déjà éliminées. Comme avant, si il n'y a pas équilibre, je marque les $3^{n-2}$ pièces puis utilise l'algorithme des pièces marquées.
-Si il y a équilibre, je continue: je pèse $3^{n-3}$ pièces, puis $3^{n-4}$ pièces etc., jusqu'à qu'il n'y ait plus équilibre pour pouvoir utiliser l'algorithme des pièces marquées (si le nombre de pièces total est comme il faut il y aura forcément un moment où il n'y aura plus équilibre)
Et vous n'avez pas défini votre tas 3, ni démontré que votre algorithme se termine et donne le résultat escompté = que cela marche...
Le voici : dés qu'on obtient un déséquilibre, on se ramene à chercher la pièce parmi $3^k$ pièces marquées en $k$ pesées, et on a vu que ça marche. Pour que l'algorithme marche il suffit donc de s'assurer qu'il ne peut y avoir équilibre jusqu'à la $n$-ième pesée incluse, où autrement dit à la $n$-ième pesée il n'y a aucune pièce restante : ce qui donne
$N=(3^{n-1}-1)+3^{n-2}+3^{n-3}+\cdots+1=\frac{3^n-3}{2}$.
Avec ce $N$ l'algorithme marche.
Et ce $N$ est effectivement optimal bien que je n'ai que brièvement évoqué le pourquoi :
en $k$ pesées, il y a $3^k$ possibilités, donc on ne peut pas trouver la pièce parmi un ensemble ayant strictement plus de $3^k$ pièces.
Donc à la $i$-ième pesée on ne peut pas mettre strictement plus de $3^{n-i}$ pièces inconnues sur la balance, et même $3^{n-1}-1$ à la première pesée pour pouvoir faire deux tas égaux. Et puisque il faut que la pièce à trouver passe nécessairement sur la balance, ça donne bien que le nombre de pièces total doit être inférieur à $(3^{n-1}-1)+3^{n-2}+3^{n-3}+\cdots+1=\frac{3^n-3}{2}$.
Si on veut juste déterminer quelle pièce est atypique, on obtient $N=\frac{3^n- 1}{2}$
14 15 16 17 18 19 20 21 22 32 33 34 38 ! 23 24 25 26 27 28 29 30 31 35 36 37 39 5 6 7 8 9 10 11 12 13 32 33 34 38 ! 14 15 16 17 18 19 20 21 22 35 36 37 39 2 3 4 11 12 13 20 21 22 23 24 25 38 ! 5 6 7 14 15 16 29 30 31 32 33 34 39 1 4 7 10 13 16 19 22 23 26 29 34 35 ! 2 5 8 11 14 17 20 25 28 31 32 37 38Pour savoir quelle est la mauvaise boule, il suffit de noter ce qui se passe pour chacune de ces 4 pesées (G si elle penche à gauche, D si elle penche à droite, et E si la balance est à l'équilibre), puis de regarder dans la liste ci-dessous
Si cela intéresse quelqu'un, je peux fournir la même chose pour 2, 3, 5 ou 6 pesées (ou au delà mais ce n'est pas raisonnable :-D)
Tout est clair, sauf la numérotation. Je n'arriverais qu'à faire les 2 premières lignes. Après la logique devient floue.
Par exemple, à 5 pesées, on laisse les 40 premières boules tranquilles, et on met 27 à gauche, 27 à droite, 9 à gauche, 9 à droite, 3 à gauche, 3 à droite, 1 à gauche une à droite. Là c'est bon. Pour la deuxième, on permutent les 27 vers la droite. Là encore, c'est bon. Et après ? 9 dernières vierges, 9 dernières des 27 de gauche, 9 dernières des 27 de droite, 9 premières des 27 disparues ? Mais pourquoi ?
Et pour les autres lignes ?
Quel est l'algorithme ? Si c'est dans le pdf, je n'ai pas compris.
Pour n = 5 on pèse 40 pièces de chaque côté à chaque pesée.