![](/img/vague-bas-gauche.png) |
#1 - 27-09-2016 08:26:08
- LeXav
- Habitué de Prise2Tete
- Enigmes résolues : 18
- Messages : 16
- Lieu: Somewhere in Nevada
Digicode gentil (mais ffaible ?)
Bonjour à tous et à toutes,
Nous connaissons tous les digicodes à 4 chiffres. Nous savons que si la solution nous est inconnue, et est purement aléatoire, il nous faut tester 10000 séquences de 4 digits avant d’être sûrs de trouver la bonne combinaison.
Cependant, pour me rendre au travail, je dois franchir un genre de digicode plutôt sympathique (true story) :
Celui-ci accepte une séquence de 8 digits, et ouvrira la porte si au sein de cette séquence se trouve la bonne combinaison. Par exemple si la combinaison est 1234 et que je tape 01234567, la porte s’ouvrira (mais elle restera close si je tape 10203040).
Tout ceci est bien pratique en cas de faute de frappe, mais je me suis demandé si cela était bien sécurisé. D’où énigme :
Combien de séquences de 8 digits faut-il tester, en se débrouillant bien, pour être sûr de tomber sur la bonne combinaison de 4 chiffres ?
(Enigme réalisée en partanerait avec Clydevil que je remercie chaleureusement)
Indice 1 : Spoiler : [Afficher le message] Il sera utile de minimiser le nombre d’occurrences d’une même combinaison de 4 chiffres dans plusieurs de nos séquences
Indice 2 : Spoiler : [Afficher le message] Que faudrait-il faire si la séquence à entrer pouvait faire une taille quelconque, au lieu de seulement 8 digits ?
***EDIT*** On peut assez simplement trouver le nombre qui validera la case réponse , mais j'attends également un argument expliquant pourquoi ce nombre est bien le bon.
Bon courage !
Xav, Le Xav
#2 - 27-09-2016 10:17:28
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Digicode getil (mais faible ?)
La réponse est 2000 : si l'on dispose d'une suite de De Bruijn pour les mots de longueur 4 avec les 10 chiffres, notée a0.a1. ... .a9999, alors il faut rentrer les 2000 séquences a0...a7 ; a5...a12 ; a10...a17 ; ... ; a9990...a9997 ; a9995.a9996.a9997.a9998.a9999.a0.a1.a2. Chacune des séquences permet de tester 5 codes différents.
#3 - 27-09-2016 17:42:05
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Digicode genil (mais faible ?)
2000 est un minimum, mais ça me parait compliqué de l'atteindre. Il existe une méthode analytique pour l'optimisation ?
#4 - 27-09-2016 20:28:38
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Digicode genil (mais faible ?)
C'est simple: En se debrouillant bien, on peut faire loger 5 sequences differentes de 4 chiffres dans une sequence de 8 chiffres. Donc pour faire tous les 10000 codes, il n'est nécessaire que je générer 10000/5 = 2000 codes à 8 chiffres. Cependant, trouver une série de 2000 codes qui n'aient aucune séquence de 4 chiffres en commun n'est pas simple! Ca devais faire l'objet d'une autre énigme.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#5 - 27-09-2016 21:48:47
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Digicode gentil (mis faible ?)
Bonjour, Sachant qu'un nombre de 8 chiffres contient 5 nombres de 4 chiffres, on peut espérer faire 10000/5 = 2000 combinaisons. J'avais déjà rencontré le problème du digicode. De bruijn nous apprend qu'il est possible de trouver un nombre de taille 9^4+3 contenant tout les nombres de 4 chiffres. En faisant une section tout les 5 chiffres et en prenant les 8 suivant la section, on trouve nos 2000 codes
#6 - 28-09-2016 08:07:00
- LeXav
- Habitué de Prise2Tete
- Enigmes résolues : 18
- Messages : 16
- Lieu: Somewhere in Nevada
Digicode gentil (mias faible ?)
Xav, Le Xav
#7 - 28-09-2016 08:38:46
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
digicode gentil (mais faoble ?)
@LeXav : je connaissais le concept et je comptais l'utiliser avant de lire ton indice, mais je ne connaissais pas le nom. Ton indice m'a donc économisé une recherche Google, et surtout, il m'a donné l'assurance que la méthode que j'envisageais était la bonne. Donc oui, c'est peut-être un peu trop évident.
#8 - 28-09-2016 09:29:20
- franck9525
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1935
- Lieu: 86310
dihicode gentil (mais faible ?)
B = base du digit de la combinaison; ici B = 10 Q = nb de digits dans une combinaison; Q = 4 L= nb de digits dans la séquence testée; L = 8 T = nb de combinaison au sein d'une sequence = L-Q+1 X = nb de test minimum
X = (B ^ Q / ( L - Q + 1)
AN: X = 10 000 / 5 = 2000
The proof of the pudding is in the eating.
#9 - 28-09-2016 14:31:13
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Digicode gentil (mais faible )?
Au fait, il y a deja 2 sujets similaires sur P2T: Digicode et Le digicode
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#10 - 28-09-2016 16:58:10
- LeXav
- Habitué de Prise2Tete
- Enigmes résolues : 18
- Messages : 16
- Lieu: Somewhere in Nevada
Digicode genttil (mais faible ?)
@Ebichu : Merci pour ce retour ![smile](img/smilies/smile.png)
@franck9525 : Oui, mais qu'est-ce qui t'assure qu'une même combinaison ne se retrouve pas dans plusieurs séquences
@dhrm77 : Tout à fait. Elle m'ont été suggérées au moment de poster celle-ci mais je ne les ai pas incluses dans mon énoncé, au temps pour moi.
Xav, Le Xav
#11 - 30-09-2016 06:07:46
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
digicode gentil (mais faoble ?)
Les 10 000 nombres, de 0000 à 9999, c'est aussi 100 fois tous les nombres ab à 2 chiffres du milieu : x ab y On commence par écrire 2 fois tous les x ab (2000 nombres). Chaque ab est présent 20 fois, et on complète par y avec 2 fois tous les chiffres de 0 à 9. Evidemment comme chaque x ab est présent 2 fois, on évite d'attribuer le même chiffre y. Quand on a fini cette opération, on a écrit 2000 nombres à 4 chiffres différents, qu'on raye de la liste des 10 000 nombres. Les 20 représentants de chaque by sont des ab qu'on complétera comme ci dessus par des y. En portant attention à attribuer à y un chiffre tel que xaby n'est pas déja rayé. Et ainsi de suite jusqu'au 8 ème chiffre, au terme duquel on aura représenté les 10 000 nombres.
#12 - 30-09-2016 07:52:02
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Digciode gentil (mais faible ?)
Il est prouvé là qu'il faut 10 003 chiffres :
http://www.prise2tete.fr/forum/viewtopic.php?id=10842
Par groupes de 8 , la première tentative en recouvre 8 et les suivante seulement 5 de plus car il faut reprendre les 3 derniers de la combinaison précédente.
Total : 8 + 1999 x 5 = 10 003 soit 2000 essais.
#13 - 30-09-2016 13:47:59
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
digicodz gentil (mais faible ?)
caduk a écrit:De bruijn nous apprend qu'il est possible de trouver un nombre de taille 9^4+3 contenant tout les nombres de 4 chiffres.
Tu voulais probablement dire 10^4 + 3 au lieu de 9^4 + 3.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#14 - 30-09-2016 14:26:32
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Digicode gentil (mais faible ?))
Je ne comprends pas les 10 003 essais. Des essais pour fabriquer les 2000 nombres de 8 chiffres ?
#15 - 01-10-2016 10:08:04
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
digicode gentil (lais faible ?)
Je n'ai rien compris aux réponses faites, mais je ne connais pas les suites de De Bruijn.
La réponse attendue se contentait-elle de faire référence à cette suite ? Si oui, l'intérêt de l'énigme est plutôt faible. Sinon, il faudrait donner une réponse plus développée.
#16 - 01-10-2016 10:39:01
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Digicode gentil (amis faible ?)
nodgim a écrit:Je ne comprends pas les 10 003 essais. Des essais pour fabriquer les 2000 nombres de 8 chiffres ?
Non, 10 003 c'est la taille d'un nombre qui contient exactement toutes les séquences de 4 chiffres une seule et unique fois.
On ne peut pas faire mieux car il y a 10 000 séquences différentes.
Comme ce nombre est constructible, il suffit d'en prendre des morceaux de longueur 8.
#17 - 01-10-2016 12:13:17
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Digicode gentil (ais faible ?)
OK, Gwen. Et comment construit-on ce nombre ?
#18 - 01-10-2016 12:50:49
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Digiocde gentil (mais faible ?)
#19 - 01-10-2016 13:23:46
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
iDgicode gentil (mais faible ?)
Merci Gwen, on y a de bons exemples, mais semble t il pas de preuve de généralisation. Je dis ça parce qu'il existe une autre méthode pour construire ces 2000 nombres sans passer par cette fameuse suite.
#20 - 01-10-2016 14:09:51
- Agid1915
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 50
Diicode gentil (mais faible ?)
Comment construire les sequences de 8 de maniere optimale est une autre question qui n`a rien a voir avec l`enigme. C`est un probleme qui, lui-meme, a un grand nombre de solutions autre que les suites de Brujin.
|
![](/img/vague-haut-droite.png) |