Les mafiosi et le banquier

freddy · 10-10-2011 10:49:48

A la suite de l'énigme posée par Fred plus tôt, il appert que l'aîné, Don Doumé, conserve tout.

Don Doumé a aussi, et entre autres, dans sa caverne de Ben Ali, 200 lingots d'or fin à 99 /100 (presque du 5-9) à propos desquels le plus jeune de la bande lui sussure qu'en réalité, un n'est pas vraiment en or, mais dans un alliage qui imite l'or a s'y méprendre. En particulier, le poids ne change pas, mais l'alliage n'est plus aussi pur, et perd considérablement de sa valeur de marché.

Don Doumé comprend qu'il n'a pas d'autre choix que d'aller voir un banquier ami de la famille pour l'aider à trouver le mauvais lingot.

Le banquier lui fait la proposition suivante : Don Doumé lui présente un lot de lingot et le banquier lui facture la recherche 3.000 euros si le faux lingot s'y trouve, 2.000 euros sinon.

La recherche continue tant que l'impur lingot n'est pas trouvé, Don Doumé n'en dort plus depuis qu'il a compris qu'il s'était fait rouler lors d'un précédent partage à la sauce calabraise.

Don Doumé, outre ses indiscutables qualités présentées par Fred, est aussi très, très, très économe de ses moyens.

Comment l'aider à dépenser une somme minimale ([tex] > 0[/tex]) pour qu'il soit certain d'identifier le faux lingot ?

En clair, quelle stratégie adopter pour minimiser ex ante le coût de l'opération vérité ?

Hint : on commencera par imaginer qu'il n'a qu'une seul lingot, puis 2, puis 3, ...

Question supplémentaire : et s'il en avait 2.503 ?

Bb

Dernière modification par freddy (11-10-2011 10:37:58)

jpp · 10-10-2011 11:45:39

Salut Freddy.

Tu veux dire qu'il faut aider Don Doumé à dépenser au maximum 2000 euros voire meme rien du tout ?

▼Ou alors

freddy · 10-10-2011 13:56:42

RECTIFICATION

il y a dans l'énoncé une légère imperfection en attente de modification !

Be cool, don't worry !

[EDIT]

Correction faite ce jour !

Dernière modification par freddy (11-10-2011 12:52:52)

totomm · 10-10-2011 14:12:56

bonjour,

freddy a écrit :

A la suite de l'énigme posée par Fred plus tôt, il appert que l'aîné, Don Doumé, conserve tout.

On a tous compris que l'imperfection était dans la première phrase ! :-)

amatheur · 10-10-2011 15:17:57

bonjour,
es ce que le banquier facture par lingot d'or analysé ? dans ce cas Don Doumé à beaucoup intérêt à choisir un banquier plus honnête que les membres de sa famille :)

nerosson · 10-10-2011 15:47:10

Salut à tous,

@Freddy,

Il me semble qu'il y a une imprécision dans ton énoncé.

Freddy a écrit :

Le banquier lui fait la proposition suivante : Don Doumé lui présente un lot de lingot et le banquier lui facture la recherche 3.000 euros si le faux lingot s'y trouve, 2.000 euros sinon.

Si après cette première transaction, Don Doumé n'est pas plus avancé (le mauvais lingot n'est pas identifié), que si passe-t-il ? Ils refont la même transaction avec un autre lot de lingots ?

D'autre part,

freddy a écrit :

Don Doumé a aussi, et entre autres, dans sa caverne de Ben Ali, 200 lingots d'or fin à 99 /100 à propos desquels le plus jeune de la bande lui sussure qu'en réalité, un n'est pas vraiment en or, mais dans un alliage qui imite l'or a si méprendre.

Il est bien évident que, si j'étais Don Doumé, pour vérifier les allégations du mafioso E, avant d' aller dépenser mon fric chez le banquier, je commencerais par partager mes lingots en deux lots de cent que je pèserais séparément : il n'y a de faux lingot que si les deux poids obtenus sont différents. Et, même si c' était le cas, j'identifierais le faux lingot sans dépenser un sou, par des pesées successives de 50, 25, 12 lingots, etc...

Dernière modification par nerosson (10-10-2011 16:06:25)

freddy · 11-10-2011 10:35:43

nerosson a écrit :

Salut à tous,
@Freddy,
Il me semble qu'il y a une imprécision dans ton énoncé.
Freddy a écrit :
Le banquier lui fait la proposition suivante : Don Doumé lui présente un lot de lingot et le banquier lui facture la recherche 3.000 euros si le faux lingot s'y trouve, 2.000 euros sinon.
Si après cette première transaction, Don Doumé n'est pas plus avancé (le mauvais lingot n'est pas identifié), que si passe-t-il ? Ils refont la même transaction avec un autre lot de lingots ?

OUI

nerosson a écrit :

D'autre part,
freddy a écrit :
Don Doumé a aussi, et entre autres, dans sa caverne de Ben Ali, 200 lingots d'or fin à 99 /100 à propos desquels le plus jeune de la bande lui sussure qu'en réalité, un n'est pas vraiment en or, mais dans un alliage qui imite l'or a s'y méprendre.
Il est bien évident que, si j'étais Don Doumé, pour vérifier les allégations du mafioso E, avant d' aller dépenser mon fric chez le banquier, je commencerais par partager mes lingots en deux lots de cent que je pèserais séparément : il n'y a de faux lingot que si les deux poids obtenus sont différents. Et, même si c' était le cas, j'identifierais le faux lingot sans dépenser un sou, par des pesées successives de 50, 25, 12 lingots, etc...

NON, pas d'écart de poids !

Dernière modification par freddy (11-10-2011 12:53:46)

freddy · 11-10-2011 10:36:44

totomm a écrit :

bonjour,
freddy a écrit :
A la suite de l'énigme posée par Fred plus tôt, il appert que l'aîné, Don Doumé, conserve tout.
On a tous compris que l'imperfection était dans la première phrase ! :-)

Pourrais tu me le prouver ? ;-)))

totomm · 11-10-2011 12:22:49

Bonjour,

freddy a écrit :

A la suite de l'énigme posée par Fred plus tôt, il appert que l'aîné, Don Doumé, conserve tout.
.
totomm a écrit :
On a tous compris que l'imperfection était dans la première phrase ! :-)

Attendons sagement la solution de Fred.....

Cordialement

freddy · 12-10-2011 16:20:03

totomm a écrit :

Bonjour,
freddy a écrit :
A la suite de l'énigme posée par Fred plus tôt, il appert que l'aîné, Don Doumé, conserve tout.
.
totomm a écrit :
On a tous compris que l'imperfection était dans la première phrase ! :-)
Attendons sagement la solution de Fred.....
Cordialement

Salut,

Pourquoi faire, tu n'es pas sûr de ta capacité à raisonner juste ? ou de la qualité de tes intuitions logiques ?

(...)

freddy · 12-10-2011 16:25:07

jpp a écrit :

Salut Freddy.
Tu veux dire qu'il faut aider Don Doumé à dépenser au maximum 2000 euros voire rien du tout ?

Heu, non seulement il est très avare, mais il a aussi toujours peur qu'on le vole ... surtout dans la famille ...

Dernière modification par freddy (12-10-2011 16:27:01)

Fred · 12-10-2011 20:13:15

Hello les jeunes :-)

Pour essayer de faire avancer le schmilblick et voir si j'ai compris, je commence comme Freddy l'a proposé :

2 lingots : j'en teste un sur les deux, si c'est le faux, j'ai dépensé 3000 euros, sinon j'ai identifié le faux pour 2000 euros. Cela fait une dépense moyenne de 2500 euros.

3 lingots : j'ai plusieurs techniques :

* je fais 3 lots de 1 lingot. Je teste le premier, un chance sur 3 qu'il soit le faux (dépense=3000 euros), je pèse le second, 1 chance sur 3 qu'il soit le faux, j'ai dépense 6000 euros, sinon j'ai identifié le faux en dépensant 5000 euros. Dépense moyenne dans ce cas : 4666 euros
* je fais un lot de 2 lingots, un lot de un lingot, et je teste d'abord le lingot unique. Il est faux (une chance sur 3), j'ai dépensé 3000 euros, sinon, j'ai 2 chances sur 3 de dépenser en moyenne 2000+2500 (se remémorer du cas 2 lingots)=4500 euros.
La dépense moyenne ici est de : 4000 (c'est mieux!)
* je fais un lot de 2 lingots, un lot de un lingot, et je teste d'abord le lot de 2 : deux chances sur 3 que le faux soit dedans, pour une dépense moyenne de 5500 euros. Si le faux n'est pas dedans, j'ai dépensé 2000 euros. Dépense moyenne : 4333 euros

Cela a l'air assez subtil....

Fred.

jpp · 12-10-2011 21:44:04

Bonsoir.

avec 1 lingot je suis sur qu'il est faux -> 0 euros
avec 2 lingots j'en présente 1 , au pire il est bon --> 3kE
avec 3 lingots j'en présente 1 , au pire il est bon, il m'en reste 2 , j'en présente 1 au pire il est faux --> 2+3=5kE
avec 4 lingots j'en présente 2 , au pire il y a le faux , et j'en présente 1 et au pire c'est lui le faux --> 3 + 3 = 6kE
avec 5 lingots j'en présente 2 , au pire il sont bons , il m'en reste 3 et j'en présente 1 , au pire il est bon , il m'en
reste 2 , j'en présente 1 et au pire c'est le faux --> 2 + 2 + 3 = 7kE.
avec 6 lingots , j'en présente 2 , au pire ils sont bons , il m'en reste 4 et j'en présente 2 , au pire ils sont bons , il
m'en reste 2 et j'en présente 1 au pire il est faux --> 2 + 2 + 3 = 7 kE
avec 7 lingots je présente 3 , au pire il y a le faux , j'en présente 1, au pire il est bon , il en reste 2 , j'en présente 1
et au pire c'est le faux --> 3 + 2 + 3 = 8 kE

à plus

Dernière modification par jpp (13-10-2011 05:56:52)

totomm · 13-10-2011 09:24:35

Bonjour,

totomm a écrit :

Attendons sagement la solution de Fred.....

@ Fred : Il s'agit bien sûr de la solution à lénigme : "Les mafiosi et la cocaïne par Fred [1 2 3]", pas de la réponse à l'énigme en cours de freddy.

Cordialement

totomm · 13-10-2011 14:30:00

Bonjour,

Est-ce que le banquier identifie le faux lingot s'il se trouve dans le lot qui lui est présenté ?
Supposons NON, sinon le problème est terminé en une fois : Don Doumé présente les 200 lingots !

Si donc, pour n lingots parmi lesquels un est douteux, don Doumé en présente q, la probabilité de payer 3000 est de q/n, et celle de payer 2000 est n-q/n.
La somme moyenne pour une présentation est de 1000 (3q+2(1-q))/n = 1000(2+ (q/n))
Quel que soit dans lequel des 2 lots se trouve le faux lingot, il faudra itérer soit sur les q lingots, soit sur les (n-q). Le mieux est donc de choisir q = n/2.
Pour 200 lingots il y aura 7 itérations soit l'espérance de ne pas dépenser plus de 7x2500 euros

Cordialement

jpp · 13-10-2011 19:19:42

Bonsoir.

suite du poste #13.

en fait sur une quantité de n lingots avec n = p + q il faut déterminer p lingots qui vont générer

autant de frais ( si le vrai appartient à p) , que si l'on présente le complément q dans lequel le faux est

abscent.

ex. n = 7 la facture s'élève à 8 kE .

Je présente alors un lot de p = 3 lingots. le faux est dedans --> 5 kE = 2 + 3 ( 3 , parce qu'il est dedant).

si j'avais présenté q = 4 lingots . le faut n'étant pas dedans alors le montant des frais aurait été de 2 + 2 ( 2 parce qu'il n'eut pas été dedans ). et là j'ai du déterminer p & q correctement car en prenant en compte le lot ou se
trouve le faux lingot j'ai les memes frais en présentant p qu'en présentant q au banquier.

car frais(p) - 3 = frais(q) - 2 = 2 kE

Je récapitule. dans le pire des cas si le faux est dans q = 4 , je présente p = 3 lingots et ça me coute 2 kE. puis je
prend le lot q = 4 dans lequel je prélève 2 lingots ,s'il est dedans je rajoute 3 kE et parmi ces 2 lingots je choisis
le faux et ça me coute encore 3 kE . ça fait bien 8 kE

si bien que les groupes se diviseraient en sous groupes et les sous groupes en groupes plus petits

avec n = 7 --> 2 groupes 3 et 4 . je prend le plus petit 3 qui se décompose en 1 + 2

avec n = 5 --> 2 + 3 et je prend 2 que je décompose en 1 + 1 .

je vais réfléchir la dessus.

à plus.

jpp · 15-10-2011 11:04:22

Bonjour.

3 lingots me coutent 5kE et 7 lingots me coutent 8kE , 8 & 9 lingots me coutent 9kE , 10 , 11 & 12 lingots me
coutent 10 kE

Donc pour faire une analyse de 12 lingots à 10kE , je présenterais pour 3kE de moins 5 lingots .

pour analyser 16 lingots à 11 kE , je présente 7 lingots à 8 kE .. etc

le rapport des frais est de 3/2 = 1.5 pour le cas ou il y a faux lingot ou non.

il faut donc trouver un rapport inférieur à 1.5 entre 2 nombres successifs d'une série récurrente.

pour cela il y a bien une suite générée par la racine de l'équation x³ - x - 1 = 0

la racine réelle de cette équation est 1.32471795724. et 1.3247..³ = 2.3247..

si j'ai la suite de nombres entiers a , b , c , d ... telle que b = ax , c = ax² et d = ax³ = a.(x + 1) ou approchante.

cette suite est une cousine de la suite de fibonacci ou F_n = F_n-2 + F_n-1

Ses termes sont les suivants 1 1 2 3 5 8 13 21 ...

l'autre suite est celle de Padovan ou U_n+1 = U_n-2 + U_n-1

ses termes sont les suivants : 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200

de terme en terme il apparaitrait que les frais augmentent de 1kE . Donc de 86 lingots à 200 lingots cela me couterait entre 1 et 3 kE de plus .

donc pour 3kE je présente 86 lingots , au pire le faux lingot s'y trouve (et ce sera comme ça jusqu'au bout)

puis je présente pour 3kE de plus 37 lingots , pour 3kE de plus 16 lingots , pour 3kE de plus 7 lingots dont

je sais déjà que ça me coute 8kE .

J'en conclus que pour 8 + 4 x 3 = 20 kE , je pourrais faire analyser 200 lingots.

je ne sais pas si Don Doumé est d'accord pour couper une barre d'un kilo en 2 pour la laisser à son cousin.

et pour 2503 lingots ce cout serait de 29kE , le meme que pour 2513 qui appartient à cette série. et je présenterais

d'abord 1081 lingots pour 3kE , puis 465 lingots pour 3 kE et enfin 200 lingots pour 3kE et 20 kE avec le cheminement précédent.

à plus.

Dernière modification par jpp (15-10-2011 11:34:33)

amatheur · 17-10-2011 13:21:08

bonjour,

excusez-moi JPP, il y a un point qui m'échappe dans votre démonstration; l’équation x3 - x - 1 = 0, d’où es ce qu'elle sort?? pour moi c'est le lapin qui sort du chapeau du magicien!

Dernière modification par amatheur (17-10-2011 13:40:57)

nerosson · 17-10-2011 14:51:06

Salut à tous,

@freddy,

Contrairement à ce que tu as affirmé a posteriori (ça n'était pas dans l'énoncé initial, que tu as complété après parution de mon post 6), un faux lingot a forcément un poids différent. Mais laissons tomber ça et admettons que tu as raison.

Je propose un lot A de cent lingots à l'expertise. Je sais alors si le lingot recherché (lingot X) est dans le lot A ou dans le lot B (les cent autres).
Je divise le lot suspect en deux lots C et D de 50 et je soumet l'un d'eux à l'expertise : je sais alors quel est le lot suspect.
Je divise ce lot en deux lots E et F de 25 et je soumet l'un d'eux à l'expertise : je sais alors quel est le lot suspect.
Je forme deux lots de 12 et je soumet le 25ème lingot à l'expertise : si c'est le lingot X : terminé. Sinon, je soumet un des lots de 12 à l'expertise et je sais quel est le lot suspect.

Et ainsi de suite, jusqu'à identification du lingot X.

Dernière modification par nerosson (17-10-2011 17:22:45)

tibo · 17-10-2011 22:17:47

Salut,

Je suis d'accord avec la solution de Nerosson,
On soumet à l'expertise la moitié des lingot du lot contenant le faux.
On divise ainsi par 2 le nombre de lingot suspect à chaque itération.
Cette méthode fonctionne et parait être la meilleure, du moins intuitivement.
Tout le problème est de démontrer que c'est la meilleure méthode...

Cela me rappelle un jeu : "retrouver en le moins de coup possible un entier compris entre 0 et x avec pour seules indications à chaque proposition si le nombre proposé était inférieur ou supérieure au nombre cherché"
J'avais lu quelque part (un vieux Tangente) que c'était un problème ouvert de trouver une méthode minimisante.
Mais l'algorithme de choisir un nombre au milieu était un excellent algorithme.
Cependant on pouvait encore l'améliorer en rajoutant une part d'aléatoire.

Je ne sais pas si ça a un quelconque rapport, mais bon...

freddy · 18-10-2011 09:54:20

Salut !

@JPP : tu participes au concours mondial de mathématiques ??? Allez Cauchy, sors de ce corps !
Et bravo !
:-)))

nerosson · 18-10-2011 13:07:19

Salut à tous,

A mon tour de dire bravo à Tibo, car si j'ai donné cette solution, je ne suis pas capable de prouver qu'il n'y en a pas de meilleure : intuitivement, j'ai tendance à le croire, mais c'est tout. La similitude avec le problème qu'évoque Tibo est évidente et il lui semble se souvenir qu'il est possible de faire mieux.

Le problème reste ouvert....

P.S. Je reviens sur la question pour me contredire moi-même (la honte, connais pas !).

Il y a tout de même une petite différence entre le problème des lingots et celui évoqué par Tibo : pour les lingots, on a deux éventualités à chaque proposition : Le lingot X est dans le lot ou il n'y est pas. Pour les nombres de Tibo, on en a trois : le nombre proposé est inférieur, ou il est supérieur, ou c'est le nombre cherché lui-même.

Dernière modification par nerosson (18-10-2011 13:25:06)

freddy · 18-10-2011 13:46:20

Salut nerosson,

que nenni ! Dans un sujet désormais connu (trouver la meilleure tactique pour détecter à partir de quelle hauteur de 100 étages se casse une bille de verre, sachant que je n'en ai que deux à ma disposition), la dichotomie est sous optimale !

Dans le cas des lingots, le cheminement proposé est meilleur que la dichotomie, comme tu viens de le comprendre.

Dernière modification par freddy (18-10-2011 13:46:42)

freddy · 18-10-2011 14:36:49

Salut,

comme on l'aura tous compris (???), le problème de Don Doumé est de détecter le lingot truqué ; la procédure avec le banquier est que ce dernier lui dit si le lingot faussé se trouve bien dans le lot proposé, sans pour autant lui indiquer lequel, auquel cas le sujet est un rare cas de trivialité.

Il faut donc trouver une cheminement qui minimise le coût des consultations successives, et donc une procédure récursive du genre : dans un lot de 5 lingots se trouve le mauvais lingot ; comment fractionner au mieux ces 5 lingots pour savoir si le faux s'y trouve et en combien d'étapes (et donc à quel coût) y parvenir.

D'où ma suggestion de démarrer avec 1, puis deux, puis trois, puis 4 lingots pour construire cette récurrence (de Padovan, bravo encore à JPP).

(...)

amatheur · 18-10-2011 15:22:55

salut
es ce qu'un vénérable quadricéphale du site pourrait donner au mononeurone que je suis une réponse pour la question que j'ai posé sur le poste #18, merci d'avance.

Forum de mathématiques - Bibm@th.net

#1 10-10-2011 10:49:48

Les mafiosi et le banquier

#2 10-10-2011 11:45:39

Re : Les mafiosi et le banquier

#3 10-10-2011 13:56:42

Re : Les mafiosi et le banquier

#4 10-10-2011 14:12:56

Re : Les mafiosi et le banquier

#5 10-10-2011 15:17:57

Re : Les mafiosi et le banquier

#6 10-10-2011 15:47:10

Re : Les mafiosi et le banquier

#7 11-10-2011 10:35:43

Re : Les mafiosi et le banquier

#8 11-10-2011 10:36:44

Re : Les mafiosi et le banquier

#9 11-10-2011 12:22:49

Re : Les mafiosi et le banquier

#10 12-10-2011 16:20:03

Re : Les mafiosi et le banquier

#11 12-10-2011 16:25:07

Re : Les mafiosi et le banquier

#12 12-10-2011 20:13:15

Re : Les mafiosi et le banquier

#13 12-10-2011 21:44:04

Re : Les mafiosi et le banquier

#14 13-10-2011 09:24:35

Re : Les mafiosi et le banquier

#15 13-10-2011 14:30:00

Re : Les mafiosi et le banquier

#16 13-10-2011 19:19:42

Re : Les mafiosi et le banquier

#17 15-10-2011 11:04:22

Re : Les mafiosi et le banquier

#18 17-10-2011 13:21:08

Re : Les mafiosi et le banquier

#19 17-10-2011 14:51:06

Re : Les mafiosi et le banquier

#20 17-10-2011 22:17:47

Re : Les mafiosi et le banquier

#21 18-10-2011 09:54:20

Re : Les mafiosi et le banquier

#22 18-10-2011 13:07:19

Re : Les mafiosi et le banquier

#23 18-10-2011 13:46:20

Re : Les mafiosi et le banquier

#24 18-10-2011 14:36:49

Re : Les mafiosi et le banquier

#25 18-10-2011 15:22:55

Re : Les mafiosi et le banquier

Réponse rapide

Pied de page des forums