Re-bonjour,
J'ai verifie ce que je voulais dire, a savoir plus precisement : dans la solution proposee plus haut, toutes les combinaisons n'ont pas ete utilisee. Il reste "de l'information" pour resoudre le probleme additionel de Michel. Les 12 premieres pierres sont traitees identiquement, et la pierre supplementaire est mise sur un des deux plateau comparee systematiquement a la pierre de reference mise sur l'autre plateau.
Cliquez pour afficher
Si vous voulez, je donne une solution generale plus bas. C'est plus interessant que mon baratin d'apres moi, mais je voulais decrire les etapes qui peuvent mener a une telle analyse (apres l'avoir fait, avec bien du mal, je realise que ce n'est pas forcement tres utile).
Voici une version constructive complete, partant du probleme initial. Supposons que l'on cherche si l'une parmi 9 pierres est differente. L'idee originale consiste a reconnaitre que la balance ne fournit pas un oui ou non, mais gauche, equilibre ou droit. Si l'on a 3 pierres dont on sait qu'une est differente, et si l'on sait deja si elle est plus lourde ou plus legere, il suffit d'en peser 2 l'une contre l'autre pour savoir laquelle est differente. Je ne donne pas plus de motivation pour deviner le procede pour les deux premieres pesees :
On cherche avec 2 pesees un groupe de 3 different des autres. Si l'on obtient deux fois le meme resultat de non-equilibre, on saura que le paquet ABC contient une pierre plus (ou moins) lourde. Sinon, le paquet ABC sert de reference pour determiner lequel des deux autres paquets l'on cherche. Enfin, a la troisieme pesee on pese 2 pierres l'une contre l'autre dans le paquet fautif. (A cette etape, on sait deja si la pierre recherchee est plus ou moins lourde). Si et seulement si toutes les pierres font le meme poids, on obtient deux fois l'equilibre. La troisieme etape peut s'ecrire symboliquement :Code:gauche | droite | cote -------------------------- ABC | DEF | GHI ABC | GHI | DEF
Et meme plus que symboliquement, on realise maintenant que l'on peut effectivement faire cette derniere pesee (meme si ce n'est pas tres utile) car les deux pierres additionelles sur chaque balance sont toutes bonnes.Code:gauche | droite | cote -------------------------- ADI | BEG | CFH
Ajoutons maintenant 3 pierres supplementaires pour resoudre le probleme a 12. Je laisse intacte la methode a 9 pierres. Deux choses a remarquer sur les deux premieres etapes de la strategie precedente :Finalement :
- Si toutes les pierres font le meme poids, la 3ieme mesure est inutile : il est donc possible de laisser une pierre sur les 12 de cote pendant les deux premieres etapes.
- Il n'est pas possible que la balance penche a gauche, puis a droite : nous pouvons donc ajouter impunement les 2 pierres restantes, une de chaque cote, et les echanger a la seconde pesee. Si elles sont toutes les deux bonnes, cela ne change rien. Sinon l'une d'entre elles est differente, cela produit la configuration pour l'instant inutilisee, et l'on peut determiner la pierre fautive a la fin
Pour le cas ou la pierre recherchee est parmi les trois J, K, ou L, la derniere etape permetCode:gauche | droite | cote -------------------------- ABCJ | DEFK | GHIL ABCK | GHIJ | DEFL ADIL | BEGJ | CFHK
- Si les deux premieres etapes on donne equilibre, de comparer L a J de reference
- Si les deux premieres etapes ont donne des resultats complementaires (gauche/droit ou droit/gauche), de comparer J (et indirectement K) a L de reference
Pour l'instant, je n'ai fait que re-formuler la solution proposee plus haut par Partage !
Il me semble que cette analyse suggere ou se trouve l'information restante (c'est le but de ma demarche !). Commencons par voir comment resoudre le cas a 4 pierres en 3 pesees plus une de reference. Je vais appeler ces 4 pierres J, K, L et M, et j'appelle O la pierre de reference. Je dispose de la suite :
Vu comme ca, c'est presque trop facileCode:gauche | droite | cote -------------------------- J | K | L K | J | L L | J | K
Si les deux premieres mesures donnent le meme resultat de non-equilibre, la pierre est soit J, soit K. Si les deux premieres mesures donnent deux resultats de non-equilibre differents, la pierre coupable est M. Si les deux premiers resultats donnent equilibre, la pierre candidate restante est L.Code:gauche | droite | cote -------------------------- JO | KM | L KO | JM | L LO | JM | K
Solution finale proposee :
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Code:gauche | droite | cote -------------------------- ABCJO | DEFKM | GHIL ABCKO | GHIJM | DEFL ADILO | BEGJM | CFHK
La solution generale pour un nombre quelconque de pierres, que j'ai retrouvee recemment dans un livre de Gardner (The colossal book of short puzzles and problems, Norton), fonctionne de la facon suivante :
- Faire la liste des
combinaisons de (0,1,2) de longueur
- Eliminer les trois combinaisons composees uniquement du meme chiffre
- Eliminer les combinaisons dont le premier couple de caracteres differents est 02, 10, ou 21. Les combinaisons admissibles sont de la forme ***01***, ou ****12****, ou ****20****
- Associer une pierre a chacune des
- A la pesee n, mettez sur le plateau de gauche les pierres ayant un 0 en n-ieme position, et sur celui de droite celles ayant un 2
- Si le plateau penche a gauche, notez 0, s'il penche a droite, notez 2, sinon notez 1
- Si la chaine obtenue apres
Cette methode permet de distinguer
Cette methode permet egalement de distinguer
je ne pretend bien entendu pas que Gardner est le premier a y avoir pense, mais bien le premier a l'avoir rendue populaire
Cette methode procede algebriquement, alors que je qualifierais l'autre methode de "geometrique" (sans pouvoir vraiment le justifier). Les symetries globales du probleme sont utilisees (comme l'elimination des permutations impaires, correspondant au fait que l'on cherche une strategie qui ne depende pas du fait que la pierre fautive soit plus lourde ou plus legere), et aboutit a un resultat qui, forcement, ne peut qu'etre une permutation du resultat propose (je l'ai verifie a la main : c'est moins penible que ce que j'imaginais en fait.) Mais l'on ne peut voir les sous-groupes de symetries qu'apres avoir termine la construction et au prix eventuel d'une permutation supplementaire.
Si j'ai ecrit tout cela, c'est vraiment pour ouvrir le concours du plus long spoiler de l'histoire de FS
-----
Envoyé par Michel (mmy) 
