Répondre

freddy · 28-10-2011 14:41:55

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.

totomm · 20-10-2011 14:41:55

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 ?

amatheur · 19-10-2011 15:42:57

salut
merci beaucoup freddy, là j'ai pigé le truc, et en étudiant la suite de de padovan, j'ai compris la présentation de jpp.
A+

freddy · 19-10-2011 13:28:00

(...)

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.

freddy · 18-10-2011 17:32:35

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.

(...)

freddy · 18-10-2011 15:25:07

amatheur a écrit :

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 !

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.

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).

(...)

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.

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.

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 !
:-)))

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...

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.

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!

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.

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums