Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-09-2016 08:26:08

LeXav
Habitué de Prise2Tete
Enigmes résolues : 18
Messages : 16
Lieu: Somewhere in Nevada

Digicode genitl (mais faible ?)

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 !



Annonces sponsorisées :

 
Réponse :

Xav, Le Xav
  • |
  • Répondre

#0 Pub

 #2 - 27-09-2016 10:17:28

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Digicode gentiil (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 : 2953

digivode gentil (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 : 2990
Lieu: Fanning Island-?-Lac Tele,Mali

digicode gentil (maos 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
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

iDgicode gentil (mais 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 egntil (mais faible ?)

@Ebichu, @caduk : Bonne réponse, et en effet bon argument. L'indice N°2 vous a-t-il aidé ? (simplement pour savoir si je devrais le remplacer par autre chose de moins évident)

@nodgim : En effet, il s'agit à présent de fournir un argumentaire pour démontrer ce nombre.

@dhrm77 : C'est bien ça le problème ! wink Sinon, comme tu dis, c'est assez trivial tongue

Merci pour votre participation big_smile


Xav, Le Xav

 #7 - 28-09-2016 08:38:46

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Digiccode gentil (mais faible ?)

@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 : 1922
Lieu: UK

Digicode gentil (mais faaible ?)

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 : 2990
Lieu: Fanning Island-?-Lac Tele,Mali

Digicode gentil (mais faibl ?)

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

Digicodee gentil (mais faible ?)

@Ebichu : Merci pour ce retour smile

@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 : 2953

Digicode gentil (mais ffaible ?)

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,470E+3

digicode gentil (mais faibme ?)

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 : 2990
Lieu: Fanning Island-?-Lac Tele,Mali

digicode gentil (mais faiblz ?)

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 : 2953

Digicoode 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 : 2953

Digicode gentil ((mais 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,470E+3

Digicode genitl (mais 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 : 2953

Diggicode gentil (mais 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,470E+3

Digicode gentill (mais faible ?)

Tu suis le lien que j'ai donné : http://www.prise2tete.fr/forum/viewtopic.php?id=10842

 #19 - 01-10-2016 13:23:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

digicode gentol (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
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 44

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

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Digicode par Autleaf
23-11-2012 Enigmes Mathématiques
P2T
21-12-2009 Enigmes Mathématiques
18-09-2015 Enigmes Mathématiques
P2T
Marathon par perceval
21-06-2008 Enigmes Mathématiques
P2T
Fromage par looozer
04-07-2010 Enigmes Mathématiques
P2T
Gâteau 52 par Vasimolo
26-02-2012 Enigmes Mathématiques
P2T
Gâteau 105 par Vasimolo
17-09-2015 Enigmes Mathématiques
P2T
Droite perpendiculaire INDICES par gabrielduflot
20-05-2009 Enigmes Mathématiques
P2T
Pyramides avec billes par dridridu34
01-06-2010 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete