Mission Impossible IV

freddy · 07-10-2009 11:46:46

Ethan doit désamorcer une bombe atomique située sous le Palais de L'Élysée.

Le mécanisme est en marche. Il reste moins de 3 minutes pour le désactiver.

Le code (qu'il ne connait pas) est formé de 3 chiffres, chacun compris entre 0 à 9, à composer sur un clavier soudé à la bombe.

Il a déjà réussi à bidouiller un "truc " de génie (des Alpages ...) de sorte qu'il lui suffit de trouver 2 des trois bons chiffres pour arrêter la procédure.

Il est seul, sans matériel électronique. Il n'a rien d'autre que sa tête pour réfléchir.

Chaque combinaison prend trois secondes pour être composée et validée.

Pourra t-il sauver la Princesse Carlita ? ...

Soudain, un trait de génie ! Il vient de se souvenir d'un très vieux résultat amusant, résultat à la limite de la tautologie : le théorème des tiroirs (si vous avez n tiroirs et n+1 paires de chaussettes, au moins un tiroir a sûrement plus d'une paire de chaussette) (Cf. Dirichlet).

En utilisant astucieusement ce principe, montrer qu'il arrive à sauver la France.

Y serait il parvenu s'il restait moins de 2 minutes ?

PS : merci à Ph. F

yoshi · 07-10-2009 12:18:22

Salut,

Ph. F. = Phileas Fogg ?
Bon ! ok ! Je -->

@+

nerosson · 07-10-2009 16:45:07

Salut, Freddy,
J'en connais beaucoup qui te répondraient :"Sil y avait une bombe sous le palais de l'Elysée, je me garderais bien de la désamorcer !!!".

Dernière modification par nerosson (07-10-2009 17:52:19)

nerosson · 07-10-2009 17:50:02

Bonsoir, tortueux Freddy,
je suis perplexe : je ne sais pas au juste si j'ai trouvé quelque chose de bon ou si c'est idiot.
Bon : je te déballe ma camelote et tu me diras ce qu'il en est. Si ça vaut rien, je me consolerai en pensant au plaisir que tu auras à me renvoyer dans les cordes....
Supposons qu'il compose 2 et 3. Ca correspond à trente combinaisons de trois chiffres :
1) 230 à 239
2) 203, 213, 223, 233, 243, 253, 263, 273, 283, 293
3) 023, 123, 223, 323, 423, 523, 623, 723, 823, 923.
En outre (comme disait le marchand de vin), ton énoncé est incomplet :
1) tu as omis de dire si les trois chiffres devaient être différents,
2) tu as omis de dire si l'essai de 2 et 7 dispensait de l'essai de 7 et 2.
Inutile de de me dire que ma réponse est encore bien plus incomplète que ton énoncé : je le sais. Mais il se fait tard et ma vieille cervelle a envie d'aller manger sa soupe.
Dis-moi seulement s'il y a une ébauche de solution dans ce que j'ai dit.

freddy · 07-10-2009 17:55:01

Salut,

bien sûr que tu commences à trouver ... ce dont je ne doute jamais ...

Pour le coté pinailleurs, tu fais encore très fort : un code est un code, non ? sur 3 positions, donc ... 030 est différent de 003 comme de 300, OK ? Sauf que là, si tu as deux bons numéros sur trois (dans l'ordre, dien sûr), ben voilà, "quelqu'un m'a dit que tu m'as sauvée" ...

freddy · 09-10-2009 16:22:49

Re,

a t-on pensé à demander à Barbichu et roro et Tibo et Fred et ... les autres. C'est un sujet de toute beauté !

Dernière modification par freddy (11-10-2009 22:14:34)

nerosson · 10-10-2009 16:27:01

Salut, Freddy,
J'essaye d'avancer petit à petit dans ton casse-tête.
Par un tour de génie des Alpes (que tu n'as pas précisé et que je suis incapable de trouver parce que je suis des Alpes, mais je ne suis pas un génie) tu as ramené à deux chiffres DANS L'ORDRE les essais à faire. On peut donc en déduire que, si l'on pouvait essayer les cent séquences de "00" à "99" on désamorcerait la bombe. Mais ça prendrait 300 secondes, soit 5 minutes. C'est beaucoup trop.
Mais on peut prouver que certaines de ces séquences sont inutiles.
La séquence "90" sert à générer les combinaisons suivantes de la bombe (voir mon intervention précédente) :
1° 900, 901, 902, 903, 904, 905, 906, 907, 908, 909
2° 910, 920, 930, 940, 950, 960, 970, 980, 990,
3° 090, 190, 290, 390, 490, 590, 690, 790, 890, 990.
Or, toutes ces combinaisons (SAUF 990) peuvent être générées au moyen d' autres séquences inférieures à 90 :
900 au moyen de "00", 901 au moyen de "01", etc...
910 au moyen de "10", 920 au moyen de "20", etc...
090 au moyen de "09", 190 au moyen de "19", etc...
Je crois pouvoir être dispensé de démontrer de la même façon que le même raisonnement peut être appliqué aux séquences "91" à "98".
Donc les séquences "90" à "98" n'ont pas à être essayées.
Je pense que la solution consiste, par des raisonnements du même genre, à ramener à 60 au plus le nombre des séquences à essayer. Mais j'en ai ma claque pour aujourd'hui. Je vais maintenant aller me taper une bonne dose de paracétamol, et, quand je pense au nombre de lecteurs qui vont en prendre aussi, je me dis que je devrais demander des royalties aux laboratoires pharmaceutiques (je te reverserai 10%).

freddy · 10-10-2009 17:16:04

Salut l'ami,

je vais énoncer plus simplement le sujet. Supposons que bon code soit XYZ. Il suffit de former XY*, ou bien X*Z ou bien encore *YZ pour sauver Princesse Carlita. Combien y en a t-il ?
En attendant, rien à voir avec tes calculs ci dessus.

Désolé, et encore bon courage.

Va un peu voir ce qu'on raconte sur le principe des tiroirs, cela devrait t'aider.

Bb

Dernière modification par freddy (10-10-2009 17:17:11)

nerosson · 10-10-2009 18:36:06

Bonsoir, Freddy,
Tu es un va-nu-pieds. Parce que moi, si j'ai n tiroirs et n+1 paires de chaussettes, j'ai une paire dans chaque tiroir, parce que la paire "n+1", je l'ai aux pieds.
Tout à fait entre nous, Freddy, je n'ai pas de tiroir. Comme dit la chanson, quand je veux changer de chaussettes, je les retourne et je les change de pied.
Quant à ton problème, tu as sûrement une solution officielle, mais, en attendant, j'ai tout de même progressé et il n'est pas dit qu'en progressant dans cette voie, je n'y arriverais pas. (toujours aussi têtu !!!)

freddy · 10-10-2009 22:40:21

Re,

j'ai relu avec attention tes séquences, c'est pas mal pour l'intuition du nombre de bonnes tentatives. Cependant, "90" écrit sous la forme "930" me donne le vertige (ligne 2). Le reste me semble correct.
Le nombre de 100 est bien entendu la première intuition, mais on peut faire mieux.
Mieux est toutefois différent de 60 !
Il n'y a pas de solution officielle, mais une manière de dénombrer correctement. Tu peux faire sans, j'ai bien un copain qui réussit à réduire le nombre de codes à essayer de 100 à 80.

bye

nerosson · 11-10-2009 15:33:07

Salut, freddy,
Je m'obstine à laisser mes chaussettes dans leur tiroir et je m'accroche, avec un entêtement qui t'agace (c'est toujours un bon côté de la chose...) à mon système d'élimination de certaines des séquences "00" à "99".
Par ailleurs, je ne comprends pas que l'emploi de "90" pour "930" te donne le vertige, pour deux raisons :
1° dans une précédente intervention (parag. 4) j'ai employé "23" pour "293" et tu n'as pas tiqué,
2° 90 pour 930 n'est que la concrétisation de ton X*Z.
D'autre part, je viens en continuant dans le système que je t'ai montré, en extrapolant les premiers résultats, d'arriver à la conclusion qu'on peut arriver au résultat cherché en ne conservant que 57 des cent "bichiffres" de "00" à "99". Ce qui permet de descendre en dessous des trois minutes.
J'envisage maintenant de vérifier systématiquement cette idée, ce qui ne va pas tarder à être long. Par conséquent, si tu n'as pas de mes nouvelles pendant un certain temps, ça ne signifiera pas nécessairement que je serai mort.
Donc, si la providence le veut, à plus tard.

tibo · 11-10-2009 22:13:24

Bonjour,

j'ai pas encore eu le temps d'y réfléchir sérieusement...
ne donne pas la réponse trop vite, j'y réfléchirai demain

freddy · 12-10-2009 18:49:14

nerosson a écrit :

Salut, freddy,
Je m'obstine à laisser mes chaussettes dans leur tiroir et je m'accroche, avec un entêtement qui t'agace (c'est toujours un bon côté de la chose...) à mon système d'élimination de certaines des séquences "00" à "99".
Par ailleurs, je ne comprends pas que l'emploi de "90" pour "930" te donne le vertige, pour deux raisons :
1° dans une précédente intervention (parag. 4) j'ai employé "23" pour "293" et tu n'as pas tiqué, je ne l'avais pas vu, sinon j'aurais crié, tu t'en doutes !
2° 90 pour 930 n'est que la concrétisation de ton X*Z. non, du tout, mais plutôt de 9*0, ce qui me va mieux
D'autre part, je viens en continuant dans le système que je t'ai montré, en extrapolant les premiers résultats, d'arriver à la conclusion qu'on peut arriver au résultat cherché en ne conservant que 57 des cent "bichiffres" de "00" à "99". Ce qui permet de descendre en dessous des trois minutes.
J'envisage maintenant de vérifier systématiquement cette idée, ce qui ne va pas tarder à être long. je confirme, il faut que tu montres que c'est le nombre minimal possible de combinaison. Cela étant, 57 n'est pas non plus exact, ce que ta vérification devrait te montrer !
Par conséquent, si tu n'as pas de mes nouvelles pendant un certain temps, ça ne signifiera pas nécessairement que je serai mort.
Donc, si la providence le veut, à plus tard.

Salut,

je donnerai la solution quand Yoshi San me le demandera, et prie le Ciel de te prêter la vie nécessaire à résoudre la conjecture de Golbach. J'ai compris que tu mélangeais allègrement torchons et serviettes, chaussettes et caleçons !

Bb

Dernière modification par freddy (12-10-2009 20:31:24)

tibo · 12-10-2009 19:58:52

Bonjour,

Je n'ai pas encore le résultat, mais déja une remarque intéressante:
Si la combinaison est de la forme XXY
Alors pour l'obtenir je dois composer XX ou XY
Donc pour éliminer toute les combinaisons possédant un double, je dois
soit composer tout les XX --> 10 codes
soit composer tout les XY (X différent de Y) --> 90 codes
le choix est vite fait

Je n'ai pas d'autre résultats concluant pour l'instant et surtout je ne vois pas comment utiliser ton théorème des tiroirs à chaussettes

freddy · 13-10-2009 13:30:05

Hello tutti,

une petite indication : considérons les deux groupes d'entiers G1 = [0, 4] et G2 = [5, 9].

Nous devons trouver 3 chiffres tirés des deux groupes d'entier => le principe des tiroirs permet d'affirmer que deux des trois chiffres du code appartiennent au même groupe G1 ou G2.

Il suffit maintenant (si on peut dire) de tirer parti de cette féconde remarque.

Bonne recherche ...

tibo · 13-10-2009 16:45:22

Bonjour,

c'est fou comment une indication si évidente donne une solution si rapidement.

le problème qui se pose est ma solution est minimale, ce qui m'étonnerai...

nerosson · 13-10-2009 18:32:56

Salut , Freddy (et les autres aussi),
J'ai bien l'impression que j'ai trouvé le moyen de combiner mes bichiffres avec tes chaussettes. Mais il se fait tard, on verra ça demain.

freddy · 13-10-2009 20:11:59

tibo a écrit :

Bonjour,
c'est fou comment une indication si évidente donne une solution si rapidement.
le problème qui se pose est ma solution est minimale, ce qui m'étonnerai...

Salut,

t'es amusant : tu dis penser avoir trouvé pour tout de suite reculer et dire que c'est sûrement faux ...

Alors, combien d'essais ?

Dernière modification par freddy (13-10-2009 20:12:35)

tibo · 13-10-2009 22:44:07

Je trouve 50, ce qui passe dans les trois minutes
mais rien ne montre que on ne peut pas faire mieux

Kellogs · 14-10-2009 08:29:03

Bonjour,

Ethan peut sauver le monde en 2 min 30 en testant les combinaisons :

000, 011, 022, 033, 044
101, 112, 123, 134, 140
202, 213, 224, 230, 241
303, 314, 320, 331, 342
404, 410, 421, 432, 443

+ celles construites de maniere identique avec les chiffres du groupe G2 (notation definie par freddy au post #15), ce qui fait 50 combinaisons en tout.

Concretement ca se construit comme ca :
chiffres des centaines 0,0,0,0,0 puis 1,1,1,1,1 etc
chiffres des dizaines 0,1,2,3,4 a chaque ligne
chiffres des unites 0,1,2,3,4 pour la 1ere ligne puis permutation de +1 a chaque fois (cad 1,2,3,4,0 pour la 2eme ligne etc)

Demo :
Comme l'a fait remarque Freddy, il y a forcement 2 elements (X et Y ou Y et Z ou X et Z) qui sont dans le meme groupe (G1 ou G2), par le theoreme des tiroirs.
Il suffit donc que toutes les combinaisons de 2 chiffres dans Gi dans les positions XY*, X*Z et *YZ apparaissent dans la liste des combinaisons que teste Ethan. Ce qui est le cas. (Les sceptiques pourront facilement verifier visuellement pour G1 avec la liste ci-dessus : les 0x en XY* et X*Z : 1ere ligne, en *YZ: 1ere colonne, etc).

freddy · 14-10-2009 08:34:17

Salut,

Construis 49 combinaisons et regarde si elles permettent de sauver Carlinettachou ?

Ou bien, enlève une combinaison et vérifie que les 49 autres suffisent encore. Si oui, réitère le procédé jusqu'à atteindre le nombre minimal. Si non, conclus !

Bonne continuation.

freddy · 14-10-2009 08:38:35

Salut Kellogs,

50 est il le nombre minimal de combinaison ?

Kellogs · 14-10-2009 08:58:31

Bonjour Freddy,

S'il l'on enleve l'un des elements a ma solution, elle ne couvre plus l'ensemble des combinaisons possibles. Ma solution est donc "irreductible".

Neanmoins, cela ne prouve pas qu'elle est optimale. (Par exemple le set { xy0 | x et y dans [0,9]} est irreductible mais sous-optimal, car de cardinal 100 et il y a des solutions de cardinal inferieur)

Tout ce que je peut dire pour l'instant, c'est que chaque combinaison que teste Ethan couvre 28 combinaisons (XYZ, on fait defiler X, Y, Z -> 30 valeurs, or XYZ compte 3 fois donc moins 2). Cela me dit qu'il faut au moins 36 (1000/28 arrondi a l'entier superieur) combinaisons pour couvrir tout le spectre [0, 999].

Bref, pour l'instant je sais juste que la(/les) solution(s) optimale(s) a(/ont) entre 36 et 50 combinaisons.

freddy · 14-10-2009 10:32:57

re,

la seule question d'importance est : peut il désamrocer la bombe en moins de 3 minutes ? si oui, le peut il en moins de 2 minutes.

Et je ne vois pas bien le lien entre nombre minimal et nombre optimal ...

bye

nerosson · 14-10-2009 14:25:09

Salut, Freddy,
Tu peux ranger tes chaussettes (lave-les avant !).
J'ai conservé mon truc de bichiffres, mais c'est ton indice concernant les groupes G1 et G2 qui m'a permis de déterminer ceux qu'il fallait conserver.
J'obtiens cinquante combinaisons à faire, soit 150 secondes, soit deux minutes et demi.
Jusqu'à présent, je ne vois pas de possibilités de descendre en dessous.

Forum de mathématiques - Bibm@th.net

#1 07-10-2009 11:46:46

Mission Impossible IV

#2 07-10-2009 12:18:22

Re : Mission Impossible IV

#3 07-10-2009 16:45:07

Re : Mission Impossible IV

#4 07-10-2009 17:50:02

Re : Mission Impossible IV

#5 07-10-2009 17:55:01

Re : Mission Impossible IV

#6 09-10-2009 16:22:49

Re : Mission Impossible IV

#7 10-10-2009 16:27:01

Re : Mission Impossible IV

#8 10-10-2009 17:16:04

Re : Mission Impossible IV

#9 10-10-2009 18:36:06

Re : Mission Impossible IV

#10 10-10-2009 22:40:21

Re : Mission Impossible IV

#11 11-10-2009 15:33:07

Re : Mission Impossible IV

#12 11-10-2009 22:13:24

Re : Mission Impossible IV

#13 12-10-2009 18:49:14

Re : Mission Impossible IV

#14 12-10-2009 19:58:52

Re : Mission Impossible IV

#15 13-10-2009 13:30:05

Re : Mission Impossible IV

#16 13-10-2009 16:45:22

Re : Mission Impossible IV

#17 13-10-2009 18:32:56

Re : Mission Impossible IV

#18 13-10-2009 20:11:59

Re : Mission Impossible IV

#19 13-10-2009 22:44:07

Re : Mission Impossible IV

#20 14-10-2009 08:29:03

Re : Mission Impossible IV

#21 14-10-2009 08:34:17

Re : Mission Impossible IV

#22 14-10-2009 08:38:35

Re : Mission Impossible IV

#23 14-10-2009 08:58:31

Re : Mission Impossible IV

#24 14-10-2009 10:32:57

Re : Mission Impossible IV

#25 14-10-2009 14:25:09

Re : Mission Impossible IV

Pied de page des forums