É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]

Réponses

  • Bonjour,

    Pour 12 j’ai deux solutions avec trois pesées :

    5 vs 5
    2 vs 2

    Ou

    4 vs 4
  • Bonjour

    Yves, as-tu bien pris en compte qu'on ne sait pas si la pièce frelatée est plus lourde ou moins lourde ?
  • Bonjour,

    Une solution générale (pas relue depuis 2016)
    b.pdf 2.1M
  • Bonjour,
    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)
  • Je suis curieux de votre version 5 vs 5?
  • Et aussi curieux de connaître 2 vs 2
  • Bonjour,

    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
  • Bonjour,

    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
  • Bonsoir,
    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
  • Bonsoir,

    Pour n = 4 le maximum c'est 39 boules/pièces, les 4 pesées sont données en bas de la page 4.
  • Soit P(n) le nombre max de boules/pièces dont il est Possible de retrouver la fausse après n pesées,
    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
    ;-)
  • Je suis d'accord avec vous si vous savez qu'il est plus plus lourde ou plus légère or là (((elle est de poids légèrement différent))) !!!
    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...)
  • Si je comprends vos notations, P(2) = 5 veut dire qu'en 2 pesées vouos pouvez déterminer quelle boule est différente et si elle est plus légère ou plus lourde.

    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.
  • Cela produit 9 événements exploitables que si vous savez que c'est une plus légère ou une plus lourde à chercher, mais comme on ne sait pas, cela change tout...
    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é)
  • Cela produit 9 événements exploitables que si vous savez que c'est une plus légère ou une plus lourde à chercher, mais comme on ne sait pas, cela change tout..
    Cela produit, a priori, 9 événements , ce que vous savez ou pas n'a aucun impact (D= droite, E= Etal, G=Gauche):
    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.
  • a. La balance est vide initialement donc à l'équilibre.
    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)
  • Dans le cas des douze pièces il y a les cartes de Cidrolin : http://www.les-mathematiques.net/phorum/read.php?2,777934
  • La question était en combien de pesés et pourquoi? Et si possible, sa généralisation... Il n'a jamais été du comment faire ces pesés...
    ...qui n'est pas la façon la plus facile d'y répondre!!!
    B-)
  • C'est pourtant ce que vous trouvez dans mon document.
  • Bonjour.

    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.

  • Bonjour,

    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...
  • Attention, la formule et la méthode que je propose non seulement identifie la fausse pièce, mais permet de dire si elle estplus légère ou plus lourde, sans cette précision, on peut ajouter une boule.
  • Ma méthode générale repose sur le principe suivant:
    -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)
  • Ce n'est pas le sujet de la question ! Elle était en combien de pesées n pour retrouver la fausse parmi N boules/pièces et pourquoi, justifier ce n, pas comment ?
    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...
  • J'ai donné une méthode avec$ $n pesées, qui donne une minoration du nombre $N$ de pièces qu'on peut traiter, même si je n'ai effectivement pas donné le calcul de ce $N$ maximal.
    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}$.
  • $N=\frac{3^n- 3}{2}$.est correct si on veut, non seulement déterminer la pièce atypique, mais aussi savoir si elle est trop lourde ou trop légère.
    Si on veut juste déterminer quelle pièce est atypique, on obtient $N=\frac{3^n- 1}{2}$
  • Oui, la différence étant que si on a alors le droit d'avoir n pesées à l'équilibre si il ne reste qu'une seule pièce à la fin
  • Pour que les choses soient claires, je donne ci-dessous les pesées à faire pour 39 boules :
       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   38
    

    Pour 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
    GGGE   39 Légère	|	GGGD   38 Lourde	|	GGEG   37 Légère	|	GGEE   36 Légère	|	GGED   35 Légère	|	
    GGDG   34 Lourde	|	GGDE   33 Lourde	|	GGDD   32 Lourde	|	GEGG   31 Légère	|	GEGE   30 Légère	|	
    GEGD   29 Légère	|	GEEG   28 Légère	|	GEEE   27 Légère	|	GEED   26 Légère	|	GEDG   25 Légère	|	
    GEDE   24 Légère	|	GEDD   23 Légère	|	GDGG   22 Lourde	|	GDGE   21 Lourde	|	GDGD   20 Lourde	|	
    GDEG   19 Lourde	|	GDEE   18 Lourde	|	GDED   17 Lourde	|	GDDG   16 Lourde	|	GDDE   15 Lourde	|	
    GDDD   14 Lourde	|	EGGG   13 Lourde	|	EGGE   12 Lourde	|	EGGD   11 Lourde	|	EGEG   10 Lourde	|	
    EGEE    9 Lourde	|	EGED    8 Lourde	|	EGDG    7 Lourde	|	EGDE    6 Lourde	|	EGDD    5 Lourde	|	
    EEGG    4 Lourde	|	EEGE    3 Lourde	|	EEGD    2 Lourde	|	EEEG    1 Lourde	|	
    EEED    1 Légère	|	EEDG    2 Légère	|	EEDE    3 Légère	|	EEDD    4 Légère	|	EDGG    5 Légère	|	
    EDGE    6 Légère	|	EDGD    7 Légère	|	EDEG    8 Légère	|	EDEE    9 Légère	|	EDED   10 Légère	|	
    EDDG   11 Légère	|	EDDE   12 Légère	|	EDDD   13 Légère	|	DGGG   14 Légère	|	DGGE   15 Légère	|	
    DGGD   16 Légère	|	DGEG   17 Légère	|	DGEE   18 Légère	|	DGED   19 Légère	|	DGDG   20 Légère	|	
    DGDE   21 Légère	|	DGDD   22 Légère	|	DEGG   23 Lourde	|	DEGE   24 Lourde	|	DEGD   25 Lourde	|	
    DEEG   26 Lourde	|	DEEE   27 Lourde	|	DEED   28 Lourde	|	DEDG   29 Lourde	|	DEDE   30 Lourde	|	
    DEDD   31 Lourde	|	DDGG   32 Légère	|	DDGE   33 Légère	|	DDGD   34 Légère	|	DDEG   35 Lourde	|	
    DDEE   36 Lourde	|	DDED   37 Lourde	|	DDDG   38 Légère	|	DDDE   39 Lourde	|
    

    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)
  • On préférerait pour n pesées.

    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.
    41->67-95->103-113->115-119  |  68->94-104->112-116->118-120
    
    Pour la deuxième, on permutent les 27 vers la droite. Là encore, c'est bon.
    14->40-95->103-113->115-119  |  41->67-104->112-116->118-120
    
    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 pesée, c'est l'algorithme, qui est dans le pdf

    Pour n = 5 on pèse 40 pièces de chaque côté à chaque pesée.
Connectez-vous ou Inscrivez-vous pour répondre.