Une question de vie ou de mort
dans Les-mathématiques
Bonjour,
Une petite énigme pour ce dernier Samedi hivernal. Elle est tirée du dernier numéro de la revue "Diagonales" éditée par le CNED, intitulé "Tout bien pesé".
Le calife Haroun al Rashid va trouver son grand vizir Jafar avec une bourse de mille pièces d'un dirham et une balance à fléau. Il lui dit :
« Parmi ces pièces, il y a quatre pièces fausses, un peu plus légères que les vraies et toutes les quatre de même poids. Je veux que tu choisisses pour moi une pièce ; si elle est vraie, je te donne un habit de brocart, et si elle est fausse, je te fais trancher la tête. Tu as le droit d'utiliser la balance seulement deux fois. »
Pouvez-vous souffler à Jafar un moyen d'être sûr de sauver sa tête ?
Une petite énigme pour ce dernier Samedi hivernal. Elle est tirée du dernier numéro de la revue "Diagonales" éditée par le CNED, intitulé "Tout bien pesé".
Le calife Haroun al Rashid va trouver son grand vizir Jafar avec une bourse de mille pièces d'un dirham et une balance à fléau. Il lui dit :
« Parmi ces pièces, il y a quatre pièces fausses, un peu plus légères que les vraies et toutes les quatre de même poids. Je veux que tu choisisses pour moi une pièce ; si elle est vraie, je te donne un habit de brocart, et si elle est fausse, je te fais trancher la tête. Tu as le droit d'utiliser la balance seulement deux fois. »
Pouvez-vous souffler à Jafar un moyen d'être sûr de sauver sa tête ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Mais comme il n'y a que 1000 pièces, c'est chiant loool.
Comme c'est un grand vizir, il peut sortir un vraie pièce de sa poche pour en faire 1001 et gagner en ne choisissant pas sa propre pièce (c'est possible)
Sinon si ses poches sont vides, y a quelques configurations à étudier, mais ce qui serait intéressant dans ce genre de jeu c'est des règles qui font que c'est pas possible et étudier les preuves que ça ne l'est pas.
Tel que je connais Jafar, ses poches contiennent plus vraisemblablement des fausses pièces.
Alain
Peut-être comme ceci:
En appelant F les pièces fausses plus légères et V les vraies, on prélève 6 pièces parmi les 1000.
On est en présence de l'une de ces cinq configurations allant de VVVVVV, VVVVVF, VVVVFF, VVVFFF, VVFFFF, on sait que F<V et qu'il y a au maximum 4 pièces F.
On présente alors deux pièces sur chaque plateau, soit un plateau penche ou soit la balance reste équilibrée.
Il reste alors une pesée pour trouver une pièce V.
[Edit: suite...]
1er cas: P1<P2.
Alors dans le plateau P2, il y a soit VV, soit VF.
Une deuxième pesée en plaçant les deux pièces de P2 sur chacun des plateaux permet d'obtenir V.
2ème cas: P1=P2, avec D1 et D2 sur le plateau P1, et D3 et D4 sur le plateau P2
Alors dans chaque plateau on a: soit VV=VV, soit VF=VF, soit FF=FF qui correspondent aux dinars D1,D2,D3,D4.
A suivre...euh (td)
Amicalement.
A chaque pesée, tu dois mettre le même nombre de pièces dans les plateaux sinon ça ne t'apporte aucun info.
Une pesée donnant un résultat déséquilibrée te fait gagner puisqu'elle t'indique un groupe avec au max une pièce légère.
A l'issue de la première pesée il semble qu'au mieux tu te retrouves avec un groupe ayant exactement 2 pièces légères, et il te reste une pesée. Ca c'est facilement acquis.
Si ce groupe est de cardinal impair, une pesée suffit ensuite à gagner (tu isoles une pièce et compare les sous-groupes restant, le plus lourd faut piocher dedans et si aussi lourds, la pièce isolée est gagnante)
Mais y a-t-il un moyen de gagner face à un sous ensemble de cardinal pair dont on sait qu'il a exactement 2 pièces légères, avec une seule pesée???
Les autres configurations sont compliquées...
Même en remplaçant "exactement 2 pièces" par "au plus 2 pièces" ca ne se transpose pas facilement.
Tu as 3 groupes G1,2,3 et une pièce isolée.
En pesant G1 et G2 il sont aussi lourds (sinon tu gagnes un groupe aura au plus une pièce légère)
en comparant ensuite la pièce isolée x avec un pièce de G3 y (qui seront aussi lourdes), si elles sont toutes les 2 légères tu sais que G1,2 contiennent au plus une pièce légère et que toutes les AUTRES pièces de G3 sont lourdes, mais tu as épuisé tes pesées et peut-être que x et y sont lourdes.
autre possibilité: tu compares en deuxième pesée G1 et G3. S'il pèsent autant, la pièce isolée est hélas légère, si G3 est plus léger, là c'est bon la pièce isolée est lourde et si G3 est plus lourd, pas d'info
On peut varier à volonté, mais vaut mieux "travailler" avec des sous-ensembles de pièces à l'arrache que de faire des tableaux, ca donnerait vite mal à la tête.
On prend 3 et 3.
Si égalité c'est gagné (ça ne peut être 6 pièces fausses, il n'y en a que 4).
Sinon on prend 1 et 1 du lot le plus lourd.
Si le fléau penche, la lourde est gagnante.
Si égalité, elles sont toutes deux bonnes, car sinon cela signifierait qu'il y a 5 pièces fausses.
Amicalement.
Il me semble qu'une de tes suppositions est erronée :
"Une pesée donnant un résultat déséquilibrée te fait gagner puisqu'elle t'indique un groupe avec au max une pièce légère. "
"sinon tu gagnes un groupe aura au plus une pièce légère)".
On peut avoir un groupe avec uniquement des bonnes pièces et un autre avec 2, 3 ou 4 pièces légères. Il y a alors déséquilibre.
Cordialement.
3>1 ou 2>0 ou 4>0 ou 2>1 ou 1>0
Le groupe le plus lourd a donc au plus une pièce légère. Ensuite, dans ce groupe, on prend 2 pièces et on les pèse. Si elles sont aussi lourdes alors elles sont lourdes.
Après comme je pensais tout haut, j'écartais d'office toutes les situations qui donnent à la première pesée un groupe plus lourd qu'un autre car c'est une situation gagnante.
????? Tu peux avoir 2 groupes de 3 dans chacun desquels 2 pieces legeres
Avec un nombre impair et 2 pesées autorisées: on écarte une pièce et on compare les 2 moitiés restantes: si elles pèsent pareilles la piece ecartée est lourde, sinon on gagne avec ma réponse à Gérard
Avec le double d'un nombre impair:
on fait 2 groupes impairs d'exactement 2 mauvaise pieces chacun (sinon rep à Gérard). Puis on prend un groupe, on écarte une de ses pièces et on pèse ses 2 moitiés: si elles pèsent autant la pièce ecartée est lourde, sinon la moitié lourde ne contient que des bonnes pièces.
Pour itérer, j'ai la flemme (et je vois pas tellement), ca ressemble un peu aux tours de Hanoi lol
Je crains que cette énigme soit sans solution car après la première pesée, en cas d'égalité il peut y avoir 0,1 ou 2 mauvaises pièces dans chaque plateau. reste donc, dans le paquet résiduel 4,2 ou 0 mauvaises pièces. Il y a donc deux informations à décoder avec une seule pesée. Cela semble assez difficile à réaliser. A suivre.
Cordialement,
zephir.
Une stratégie gagnante serait la donnée d'un premier couple de sous-ensemble de 1000 de même cardinal suivi de 3 couples idem suivi pour chacun de 3 éléments de 1000. Ce qui fait un arbre de hauteur 3 avec 9 feuilles et donc bcp d'arbres à essayer. Même si le premier départ est forcément sur "pèsent aussi lourd"...
à Zephir: non, on ne peut pas tellement conclure si facilement à l'inexistence d'une solution car si 1000 était impair ou le double d'un nombre impair ce serait facile.
La stratégie continue en jouant face à cette réponse 2 autres ensembles C et D disjoints et de même cardinal tels que quelle que soit la réponse qu'on lui fournira, elle brandit ensuite un élément x de 1000 qui n'est pas léger et on n'a alors aucun moyen de "révéler" à postériori les contenus des A,B,C,D de manière à rendre x léger tout en étant cohérents avec les réponses fournies.
Lorsque $n$ est impair $ > 7$ je ne vois pas comment faire.
Amicalement,
zephir.
Cela tend à confirmer mon impression, lorsque $n$ est pair. Après la première pesée, et en cas d'égalité, la distribution des fausses pièces est $0,0,4$, $1,1,2$ ou $2,2,0$. Il faut discriminer entre ces deux situations et trouver une bonne pièce en une pesée.
On attend la solution de Bu qui peut déjà nous dire si l'énigme a ou non une solution.
La première pesée doit faire déjà $p,p,2$, et dans la seconde, on doit regarder de quel côté penche la balance
je propose ceci :
- on prend 5 pièces parmi les 1000 : ce tas contient nécessairement une bonne pièce
- on en met une à l'écart parmi les 5
- on fait deux tas de deux que l'on met dans la balance à fléau
=> Si déséquilibre alors alors le plateau le plus lourd a au plus une mauvaise pièce,
==> on pèse ces deux pièces : si équilibre j'en ai deux bonnes, si déséquilibre je choisis la plus lourde
=> Si équilibre je choisis un des plateaux et je pèse ces deux pièces
==> Si équilibre je choisis celle qui est mise à l'écart sinon et ben la plus lourde.
S
Cependant si celle qui a été mise à l'écart est fausse et les 4 autres bonnes, il y aura équilibre mais c'set la fausse qu'on sélectionnera, non ?
Quel est ton choix à la 3eme ligne ?
"La première pesée doit faire déjà $p,p,2$"
Je ne comprends pas bien ce que tu veux dire par là. Ou si c'est ce que je comprends (2 pièces de côté, 499 dans chaque plateau), je crains pour ta tête.
S
Mais il faut bien une 1ere pesée $(p,p,q)$
Question quel est le choix $(p,q)$ qui apporte le maximum d'information ?
S'il y a une solution, et Bu a confirmé qu'il existe effectivement une solution, celle ci est certainement accompagnée d'une grosse arnaque...
Amicalement.
Je peux révéler la fin de l'histoire, telle qu'elle est raconté dans la mille-deuxième nuit : l'esclave dévouée de Jafar lui a soufflé une méthode infaillible pour déterminer une vraie pièce. Jafar a suivi les conseils de son esclave et, émerveillé par sa sagesse, l'a immédiatement épousée.
Il ne vous reste plus qu'à trouver ce que l'esclave de Jafar lui a glissé au creux de l'oreille. Et, je le répète, il n'y a pas d'arnaque.
Cas 1: A est plus lourd que B. A contient zéro ou une fausse pièce. Comparons deux pièces de A : si elles ont le même poids, elles sont bonnes, sinon la plus lourde est bonne.
Cas 2 : A et B ont le même poids. C a un nombre pair de fausses pièces :
Prenons 1 pièce de A, ajoutons la au dessus de la pile B, et comparons B' avec C.
Cas 2.1 : B' et C sont équilibrés. C avait 2 fausses pièces, la fausse pièce de A a été versé dans B. Les pièces restant de A sont bonnes.
Cas 2.2 : B' est plus lourd que C. C a 2 ou 4 fausses pièces, la pièce de A posée au dessus de la pile B est bonne.
Cas 2.3 : B' est plus léger que C. Les pièces de C sont bonnes.
Il semble que dans le cas 2.1, C pourrait aussi n'avoir aucune fausse pièce.
Et ce serait alors une bonne pièce qui aurait été transférée, si l'équilibre est maintenu.
Nouvelle tentative :
On prend 2 et 2.
Si écart, facile de trouver la bonne.
Si équilibre, il y a 0, 2 ou 4 fausses pièces (si je ne m'abuse, probabilité de ce cas d'environ 1 sur 40 millions).
Maintenant on remplace trois pièces.
Si on avait 4 fausses pièces le plateau lourd comporte 2 bonnes.
Si on avait 2 fausses pièces on peut avoir amené 0, 1 ou 2 fausse(s) pièce(s) et respectivement 3, 2 et 1 bonne(s).
...Ca ne marche pas, on peut avoir remplacé une fausse et deux lourdes par leurs alter ego...
Et si au lieu de 3 on remplace par 1 ou 2 le même ennui peut se produire.
Toujours pas trouvé.
@Félix : la solution de Benoît Rivet est correcte.
Ah oui en effet, pardon Michel, j'étais persuadé avoir ponctué ma phrase par un smiley.
Très joli, Benoit.
Amicalement.
Merci
Si $n=12$ (ni de la forme $2p+1$, ni de la forme $4p+2$, ni de la forme $3p+1$), y a-t-il une solution en deux pesée pour trouver une bonne pièce?
En plus il parait difficile de le programmer sur un ordi (faudrait qu'il rame pour arriver à 333 par exemple)...
Deuxiememo, j'ai loupé un truc ou, avant de se préoccuper de $n=12$, il y a $n=8$ à étudier,
Troisiememo, Benoit R, bravo et ... question indiscrète, cela vous est venu comme ça où il y a quelque chose qui vous a guidé ?
S
Lorsque n=3p+k avec k=1 ou 2 et p>2, on fait deux piles de p pièces, si elles ont le même poids, on transfère k pièces de A sur B et on conclut en comparant avec C.
Lorsque n=3q et q>4, on fait deux piles de q-1 pièces, si elles ont le même poids, on transfère 3 pièces de A sur B et on conclut en comparant avec C.
Bref : à partir de n=13, on peut conclure. Pour n=12, on n'a pas assez de pièces (ou d'imagination) :-/