Les douze pièces, et plus.

[louloute/Qc]

Bonjour,

J’imagine que tout le monde connaît les deux solutions au problème des douze pièces, à tout hasard je rappelle l’énoncé :

• Vous avez douze pièces de monnaie dont une seule est fausse
• La pièce fausse est soit plus lourde, soit plus légère
• Vous disposez d’une balance Roberval et vous n’avez droit qu’à trois pesées

Vous devez déterminer quelle pièce est fausse et si elle est plus lourde ou plus légère.

Donc pour ceux qui connaissent. La question subsidiaire : si on avait droit à 4 pesées, parmi combien de pièces pourrait-on trouver la fausse ; pour 5 pesées, 6…
-----

[PPathfindeRR]

Bonjour,

pour 6 pesées, je pense que la réponse est simple, mais avec 4 ou 5 pesées, je ne sais pas trop !

 Cliquez pour afficher

Si on converti les 12 billes par 12 lots (de 4 billes)
Si on suit la même logique que la solution de l’énigme originale, on peut déduire le lot qui contient la bille intrus.
Si on prend le lot contenant la bille intrus, + deux autres lots, tous maintenant connus
Soit avec 3 lot (de 4 bille), on applique simplement la solution de l’énigme originale.

Si on part sur 12 lots (de 4 billes), ça nous donne : pour 6 pesées, un total de 48 billes,

Pour 4 ou 5 pesée, je donne ma langue au chat,
Car les billes sélectionnées lors de la 2ème et 3ème pesée varient, vu qu’elles sont en fonction du résultat de la 1ère pesée. (cas initial d’équilibre ou de déséquilibre).

[PPathfindeRR]

Si ma réponse est incomprise, c'est en fonction de ma solution pour l'énigme originale, qui dans ce cas serait fausse.

je vous met donc ma solution de l'énigme originale (qui pour moi est logique) :

[Amanuensis]

12 = (27-1)/2 - 1

Notons qu'on peut améliorer un tout petit peu l'énoncé:

• Vous avez douze pièces de monnaie dont au maximum une seule est fausse

Vous devez déterminer s'il y a une pièce fausse, et si oui quelle pièce est fausse et si elle est plus lourde ou plus légère.

[A voir en vidéo sur Futura]

[Amanuensis]

je vous met donc ma solution de l'énigme originale (qui pour moi est logique) :

Il y a une solution sans pesée conditionnelle: les trois pesées sont décrites avant la première pesée, et le résultat une fonction univoque du résultat des trois pesées. Pour moi c'est "plus logique".

[PPathfindeRR]

Il y a une solution sans pesée conditionnelle: les trois pesées sont décrites avant la première pesée, et le résultat une fonction univoque du résultat des trois pesées. Pour moi c'est "plus logique".

Bah ce n'est pas ce que je fais dans mes deux solutions ?!

Pour ma part je détermine les deux pesée suivante en fonction du résultat de la première.
Je peux donc décrire les trois pesées (différentes selon pesée initiale) avant d'effectuer la première pesée.

les trois pesées sont décrites avant la première pesée "effectuée"

Dans un cas d'équilibre je détermine les 2 pesées suivantes
Dans un cas de déséquilibre je détermine les 2 pesées suivantes différentes.
Les billes peuvent être dans le désordre, mais le principe de sélection des billes pour la deuxième pesée reste le même.
D'ailleurs, refaire ce même principe avec les billes numérotée dans le désordre, permet de contrôler la bonne logique de la procédure.

[Médiat]

Bonjour,

J'avais écrit cela il y a plus de 7 ans (je ne l'ai pas relu) :

[louloute/Qc]

Bravo à PPathfindeRR pour la solution essai-erreur et à Médiat pour la généralisation.

Pour la solution sans essai : mes pièces s'apellent 1,2...9, A, B, C.

12_Pièces_2.jpg

[Amanuensis]

Bah ce n'est pas ce que je fais dans mes deux solutions ?!

Pour ma part je détermine les deux pesée suivante en fonction du résultat de la première.

La deuxième phrase indique que la réponse à la question est non.

[Amanuensis]

Un exemple de trois pesées indiquées à l'avance, indépendantes de tout résultat:

3 4 10 9 vs. 6 7 12 1
7 11 1 9 vs. 8 10 12 2
5 8 1 9 vs. 4 6 7 2

(Ce n'est pas généré au hasard ou par essais et erreurs, mais par une méthode systématique applicable à tout nombre de pesées. La solution est applicable au "problème complet"--1 bille de bon poids disponible et possibilité que toutes les billes soient bonnes.)

[Amanuensis]

Par ailleurs, toutes les réponses sont sur le forum depuis des années. La plus ancienne "complète" dans mes notes personnelles est de fin novembre 2005.

[ansset]

ps : @pathfinder :
ta solution à 6 tirages est perfectible, tu peux en sélectionner beaucoup plus ( 364 )
( voir le post d'Amanuensis qui donne implicitement la formule pour n tirages, et la démonstration complète de Médiat )
avec 4 tirages, on peut tirer déjà 40 boules..

[Amanuensis]

Pour la solution sans essai : mes pièces s'apellent 1,2...9, A, B, C.

Oops... J'avais manqué ce message. Désolé pour le "doublon".

[PPathfindeRR]

ta solution à 6 tirages est perfectible, tu peux en sélectionner beaucoup plus ( 364 )
( voir le post d'Amanuensis qui donne implicitement la formule pour n tirages, et la démonstration complète de Médiat )
avec 4 tirages, on peut tirer déjà 40 boules..

et plus encore, effectivement !

Par ailleurs, toutes les réponses sont sur le forum depuis des années. La plus ancienne "complète" dans mes notes personnelles est de fin novembre 2005.

Je n'y ai pas pensé et.....
je suis parmi vous que depuis 2013 !
c'est pas une excuse ? je sais !

par contre j'ai du mal à comprendre votre procédé pour la solution de l'énigme originale

[Amanuensis]

Je n'y ai pas pensé et.....
je suis parmi vous que depuis 2013 !
c'est pas une excuse ? je sais !

Pas besoin d'excuse.

C'est plutôt le contraire: perso je pense qu'il faut limiter les références à des discussions et textes anciens (publiés sur ce forum ou ailleurs), du moins au début d'un nouveau fil d'énigme. Ce pour laisser les "nouveaux" chercher et discuter par eux-mêmes, au minimum jusqu'à ce qu'une réponse valide ait été donnée à l'énigme telle que posée.

[Sund]

Ça m'a pris trois jours, mais j'ai trouvé la solution pour un nombre quelconque de pesées !
En plus la démonstration fournit un algorithme pour déterminer les pesées ! C'est assez informel (mon prof de maths me taperait sur les doigts si j'en avais un, mais ça marche.
Hop :

 Cliquez pour afficher

Soit p le plus grand nombre de pièces parmi lesquelles on peut trouver la fausse pièce en n pesées au maximum. p est également défini comme le cardinal du plus grand ensemble de pièces parmi lesquelles on peut trouver une unique fausse pièce en n pesées au maximum.
Nous nous proposons de montrer que 3p est le cardinal du plus grand ensemble de pièces au sein duquel on peut trouver une unique fausse *pièce en exactement n+1 pesées. Soit E *un ensemble de pièces dont exactement une est fausse, avec Card{E}=3p
Étape 1 : montrons qu'il est possible de trouver la fausse pièce en n+1 pesées au maximum *dans E.
Il existe une partition de E en 3 sous ensembles E1,E2,E3, tous trois de cardinal p. On place E1 sur le plateau de droite et E2 sur celui de gauche. Si la balance penche d'un cote la fausse pièce est de ce côté et on peut la trouver en n pesées par définition de p. Si la balance est à l'équilibre, la fausse pièce est dans le tas de p pièces restant et on peut la trouver en n pesées au maximum. Avec la pesée initiale, les deux possibilités donnent que l'on peut trouver la fausse pièce en n+1 pesées au maximum.
Étape 2 :
Montrons que dans F, ensemble de pièces de cardinal 3p+1 dont exactement une est fausse, il existe un cas ou il est impossible de trouver la fausse pièce en moins de n+2 pesées.
Toutes les partitions possibles de F contiennent au moins un sous-ensemble de cardinal p+k, avec k>=1.*
Pour prouver qu'il est impossible de trouver la fausse pièce en n+1 pesées dans F, il suffit d'examiner le cas ou un seul sous-ensemble de la partition est de cardinal p+1.
Les partitions contenant un seul sous-ensemble de cardinal p+1 peuvent s'écrire {F1, F2,F3 | (Card{F1}=Card{F2}=p)^(Card{F3 }=p+1)}
Ce qui se lit : F1 et F2 contiennent p pièces chacun, F3 contient p+1 pièces.
La première pesée se fait nécessairement entre F1 et F2. Pour gagner du temps dans la démonstration je n'examine que le cas ou la balance est à l'équilibre : la fausse pièce est dans F3 de cardinal p+1.*
Par définition de p, il est impossible de toujours trouver la fausse pièce en moins de n pesées dans F3. L'étape 1 montre alors qu'il faut au maximum n+1 pesées pour trouver la fausse pièce dans F3 (Card{F3}<=3p) *En comptant la première pesée, il faut donc n+2 pesées au maximum pour trouver la fausse pièce dans F.
3p est donc le plus grand nombre de pièces parmi lesquelles on peut trouver la fausse pièce en n+1 pesées au maximum.
Étape 3 : établissement d'une relation directe entre le nombre de pesées et le nombre maximum de pièces parmi lesquelles on peut trouver une fausse pièce.
Avec 1 pièce, il est impossible d'effectuer la pesée. Avec deux pièces et trois pièces, une seule pesée suffit. Avec 4 pièces, il faut deux pesées.
3 est donc le plus grand nombre de pièces parmi lesquelles on peut trouver la pièce en une seule pesée au maximum.
Les étapes 1 et 2 donnent :
Pn=3^n
Avec Pn le cardinal du plus grand ensemble au sein duquel on peut trouver la fausse pièce, et n le nombre de pesées.
Vous pouvez vérifier qu'on peut trouver la fausse pièce en moins de 2 pesées pour tous les entiers inférieurs ou égaux à 10 et qu'on peut la trouver en moins de 3 pesées pour tous les entiers inférieurs ou égaux à 27 (j'ai vérifié). Je n'ai pas fait les calculs jusqu'à 89 (il faut 4 pesées : 3^4=89).a démonstration fournit un algorithme facilement programmable pour trouver la fausse pièce dans un ensemble de taille quelconque.

Prière de corriger s'il y a un oubli dans la rédaction, j'en fais souvent.

[Sund]

Il y a une petite erreur dans la fin de mon article précédent : il faut lire "moins de deux peséeS pour tous les entiers inférieurs ou égaux à 9", pas a 10.
Dans les notations logiques, ^ veut dire "et", dans la formule finale, il signifie "exposant".
Voilà.

[Médiat]

Bonjour,

On place E1 sur le plateau de droite et E2 sur celui de gauche. Si la balance penche d'un cote la fausse pièce est de ce côté

Non puisque l'énoncé précise :

La pièce fausse est soit plus lourde, soit plus légère

Vous pouvez regarder là : http://forums.futura-sciences.com/sc...ml#post4772799

[Sund]

Quand je disais que j'étais tête en l'air...
Bon, si on sait que la fausse pièce est plus lourde, la démonstration marche. Il faut juste savoir en combien de pesées supplémentaires on déterminé SI elle est plus lourde ou plus légère. Je m'y remets immédiatement. Merci pour la correction.

[Médiat]

C'est toujours intéressant de chercher, mais les solutions sont déjà sur ce fil.

[Sund]

Est-ce qu'on a le droit de marquer les pièces ? Ça accélère grandement la vitesse de résolution, parce que ça évite une redondance dans les cas ou on a des nombres de pièces impaires. L'énoncé ne précise pas "vous n'avez qu'une balance et rien d'autre". Dans le doute je résouds sans marquer les pièces.

[Médiat]

Bonjour,

Je poste ci-dessous quelques démonstrations et surtout une méthode qui permet de déterminer directement, et a priori, les pesées à mettre en place pour déterminer la boule ne faisant pas le bon poids.

Je serais surpris qu'aucune faute ne soit présente dans ce document, merci de le critiquer, en particulier si certains passages ne sont pas clairs, je peux développer.

[Amanuensis]

Cela à l'air d'être ce qui a été décrit dans un fil ancien, novembre 2005 sauf erreur.

[Médiat]

Peut-être, je n'étais pas né.

[Amanuensis]

Cela est resté lisible depuis, à disposition de tout le monde, et donné en lien plusieurs fois il me semble.

Au passage je serais intéressé à savoir s'il y a eu une publication de cette solution constructive utilisant la base 3 alternée avant que cela apparaisse sur ce fil à cette époque.

[LPFR]

Bonjour.
Je ne me suis pas tapé toutes les discussions sur ce problème et ne sais pas si quelqu’un a déjà donné l’approche par la théorie de l’information.
Je vous la donne car je l’ai trouvé très intéressante.
Elle ne donne pas la manière de résoudre le problème, mais donne le nombre de pesées minimal.
Le nombre de cas possibles est de 24. Donc, le nombre de bits d’information est
log₂ 24 = 4,585 bits.
Comme chaque pesée peut donner 3 résultats, le nombre de bits d’information que chaque pesée peut donner est de log₂ 3 = 1,585 bits.
Donc, avec 3 pesées cela devrait suffire. Mais, attention, le nombre de bits d’information d’une pesée n’est de 1,585 que si les trois issues sont équiprobables.
Cela ne donne pas la solution, mais suggère que la première pesée doit comparer 4 pièces à 4 autres.
J’ai trouvé ça dans le petit bouquin (100 pages) « Théorie de l’Information » de Gordon Raisbeck
Au revoir.

[Médiat]

Bonjour LPFR,

Ce qui me dérange avec cette méthode c'est que pour 2 boules la réponse est fausse (en 2 pesées on ne peut pas), et pour1 boule aussi c'est faux.

D'ailleurs pour 4 boules la réponse est aussi fausse, je pense donc que cela ne répond pas à la question, mais plutôt à la même question mais en disposant de boules supplémentaires connues comme "normales".

[LPFR]

Bonjour Mediat.
Vous avez oublié un autre cas pour lequel le calcul est faux ou ne s’applique pas : c’est le cas pour zéro pièces. (Pour moi ça rentre dans la même catégorie que 1 ou 2)

Par contre, pour le cas de 4 pièces, le calcul est bon : deux pesées. Et la solution facile à trouver :
- on compare A et B
- si A = B c’est C ou D qui est fausse. Alors on compare A et C.
- si A ≠ B c’est A ou B qui est fausse. Alors on compare A et C.

Ceci dit, j’ai parlé de cette approche car elle m’avait beaucoup surpris et plu quand je l’ai lue (il y a plusieurs décennies). Et le petit bouquin remplace très avantageusement un polar pour les vacances. Je vous le recommande.
http://www.amazon.fr/THEORIE-LINFORM...ordon+Raisbeck
Au revoir.

[Médiat]

Par contre, pour le cas de 4 pièces, le calcul est bon : deux pesées. Et la solution facile à trouver :

Ce n'est pas la même question, car cela ne permet pas de savoir si la pièce est plus lourde ou plus légère :

Vous devez déterminer quelle pièce est fausse et si elle est plus lourde ou plus légère.

Et cela reste faux pour 1 ou 2 pièces.

Le calcul revient à dire que pour pièces il y a solutions, et chaque pesée ne peut donner que 3 informations, on doit donc avoir ce qui donne bien (quelque soit la base du logarithme, le résultat est le même), mais cela donne une borne inférieure, pas une solution (d'ailleurs je me sers de ce résultat dans mon document).

[Sund]

Bonjour. Est-ce que vous saviez que sans numéroter les pièces il est impossible de trouver la fausse parmi 12 pièces, et que 11 est le nombre maximum parmi lequel on peut la trouver ? Il est toutefois impossible pour 11 pièces de trouver si elle est plus lourde ou plus légère. Le maximum avec 3 pesées en respectant l'énoncé est 10.
Oui je suis un peu HS. Mais c'est toujours bon à savoir, non ? Je propose une autres énigme : trouver le nombre maximum de pièces parmi lesquelles on peut trouver la fausse en moins de n pesées sans qu'on ait le droit de numéroter les pièces.