Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#26 18-10-2011 15:25:07
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Les mafiosi et le banquier
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ée sur la page #18, merci d'avance.
Attends mon grand, ça va viendre, je vais rédiger une solution qui t'y conduira directement !
Hors ligne
#27 18-10-2011 17:32:35
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Les mafiosi et le banquier
Re,
donc il faut commencer par la fin, savoir comment faire si j'ai un seul lingot ? Là c'est simple, on sait que c'est lui le faux, donc le coût est nul.
S'il m'en reste 2, j'en soumets 1 au banquier. Soit il est faux, et ça m'a coûté 3 k€, soit c'est l'autre, et il m'en aura coûté 2 k€ pour le savoir. Donc au pire, je retiens 3 k€.
Supposons maintenant que j'en ai 3. Je peux former le couple [tex](1,2)[/tex] et le couple [tex](2,1)[/tex], le premier terme du couple désignant le nombre de lingot soumis au diagnostic du banquier.
J'appelle [tex]CT(p)[/tex] le coût "pire cas" pour diagnostiquer le lingot bidonné s'il m'en reste p.
Ainsi, je sais déjà que [tex]CT(1)=0[/tex] et [tex]CT(2)= 3 k€[/tex].
Pour le couple (1,2), si le lingot soumis est faux, il m'en coûtera 3 k€, sinon il m'en coûtera [tex]2 + CT(2) = 5 k€[/tex].
Pour le couple (2,1), soit le mauvais lingot se trouve dans les 2 soumis, et je dois payer [tex]3 + CT(2) = 6 k€[/tex], soit c'est le lingot restant, et j'ai dû m'acquitter de 2 k€.
je suis pessimste et je me dis que ça va toujours me coûter le plus cher. Mais je suis raisonnablement optimiste (un pessimiste est un optimiste clairvoyant) et je me dis que je vais choisir la solution la moins chère parmi les plus onéreuses, c'est à dire un Min(Max).
Dans ce cas, je vois qu'il faut retenir le couple (1,2) et que le [tex]CT(3)=5 k€[/tex].
Continuons avec 4 lingots et calculons CT(4). On a trois couples possibles : (1,3), (2,2) et (3,1).
Dans le premier cas, soit il m'en coûte 3 k€, soit il m'en coûtera 2+CT(3)=7 , donc au pire 7 k€
Dans le second cas, il m'en coûtera soit 3 + CT(2) = 6, soit 2 + CT(2)= 5 , donc au pire 6 k€
Dans le troisème cas, il m'en coûtera 3+CT(3) = 8 k€, ou bien 2 k€ seulement, donc au pire 8 k€
La meilleur stratégie est donc (2,2) et on a CT(4)= 6 k€.
Généralisons : soit p le nombre de lingot et k le lot soumis au banquier.
Finalement, on cherche le nombre entier [tex]k^*[/tex] qui rend minimum les montants suivants :
[tex]Max\left(3+CT(k), 2+CT(p-k)\right)[/tex] quand k varie de 1 à p-1.
Et on pose [tex]CT(p) =Max\left(3+CT(k^*), 2+CT(p-k^*)\right)=Min_{k \in (1,p-1)}Max\left(3+CT(k), 2+CT(p-k)\right) [/tex].
Il se peut que [tex]k^*[/tex] ne soit pas unique, mais ce n'est pas un problème en soi et c'est ce qui va permettre d'avancer un peu plus loin.
(...)
Dernière modification par freddy (19-10-2011 13:28:47)
Hors ligne
#28 19-10-2011 13:28:00
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Les mafiosi et le banquier
(...)
On observe quelque chose d'intéressant qui va donner la direction des investigations à conduire.
On a [tex]CT(1)= 0[/tex] ; [tex]CT(2)= 3[/tex] ; [tex]CT(3)= 5[/tex] ; [tex]CT(4)= 6[/tex] ; [tex]CT(5) = 7[/tex] ; [tex]CT(6\; ou\; 7) = 8[/tex] ; [tex]CT( 8\; ou\; 9) = 9[/tex] ; [tex]CT(10\; à\; 12) = 10[/tex] ; [tex]CT(13\; à\; 16) = 11[/tex] ; [tex]CT(17\; à\; 21) = 12[/tex]; ...
A partir de [tex]p = 3[/tex], les coûts sont des nombres entiers successifs, ce qu'on prouvera plus tard.
On voit ainsi que pour un coût total de 12 k€, on peut trouver le mauvais lingot dans un effectif total maximal égal à 21. Pour 11 k€, l'effectif maximal est égal à 16, pour 10 k€, il est égal à 12, et pour 9 k€, il est égal à 9.
On subodore une relation de récurrence. Pour 13 k€, je dois pouvoir détecter le mauvais lingot dans un effectif total maximal égal à [tex]28 = 12 + 16[/tex], de la même manière que pour 1 k€ de moins, le nombre p maximal est égal à [tex]21 = 12 + 9[/tex] ...
Finalement, en se donnant un coût total égal à X k€, on en déduit l'effectif maximal correspondant, soit [tex]NB(X)[/tex], et on vient de voir que la stratégie idéale pour un coût en euros donné est de proposer [tex]NB(X-3)[/tex] lingots, et si le mauvaix n'est pas dans ce lot là, il reste X-2 k€ permettant de le trouver dans le lot de[tex]NB(X-2)[/tex] lingots, soit [tex]NB(X) = NB(X-2)+NB(X-3)[/tex]
D'où la solution fournie par JPP.
Dernière modification par freddy (19-10-2011 13:54:28)
Hors ligne
#30 20-10-2011 14:41:55
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Les mafiosi et le banquier
Bonjour,
Plusieurs questions sont intéressantes après l'exposé de ces résultats
1 : Quelle relation avec une stratégie qui considérerait la dépense moyenne minimale (voir post # 12 par Fred)
2 : Que devient la suite des paquets si au lieu de 3 et 2 en K€ on avait 5 et 3 ou même 3,5 et 2 ?
Hors ligne
#31 28-10-2011 14:41:55
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Les mafiosi et le banquier
Salut,
il me reste à prouver l'assertion : à partir de [tex]\forall p \ge 3,\; CT(p+1) = CT(p)\;ou\;CT(p+1) =1+CT(p)[/tex]
Supposons qu'il existe [tex]q > 3[/tex], plus petit nombre entier tel que [tex]CT(q+1) > 1 + CT(q)[/tex]
Par définition de la fonction coût total [tex]CT[/tex], cela signifie qu'il existe deux entiers [tex]a[/tex] et [tex]b[/tex] tels que :
[tex]CT(q) = Max[3+CT(a), 2+CT(q-a)][/tex] et [tex]CT(q+1) = Max[3+CT(b), 2+CT(q-b)][/tex]
En particulier, on a :
[tex]1+Max[3+CT(a), 2+CT(q-a)] < CT(q+1) \le Max[3+CT(a), 2+CT(q+1-a)][/tex]
et
[tex]1+Max[3+CT(a), 2+CT(q-a)] < CT(q+1) \le Max[3+CT(a+1), 2+CT(q-a)][/tex]
On en déduit que soit : [tex]1+CT(a) < CT(a+1)[/tex], ou bien [tex]1+CT(q-a) < CT(q-a+1)[/tex] ce qui contredit l'hypothèse que le nombre q était le plus petit nombre vérifiant l'inégalité stricte.
Hors ligne