Enigme Digicode gentil (mais faible ?) @ Prise2Tete

LeXav · #1

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]

Indice 2 :
Spoiler : [Afficher le message]

***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 !

Ebichu · #2

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.

nodgim · #3

2000 est un minimum, mais ça me parait compliqué de l'atteindre.
Il existe une méthode analytique pour l'optimisation ?

dhrm77 · #4

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.

caduk · #5

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

LeXav · #6

@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 ! Sinon, comme tu dis, c'est assez trivial

Merci pour votre participation

Ebichu · #7

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

franck9525 · #8

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

dhrm77 · #9

Au fait, il y a deja 2 sujets similaires sur P2T:
Digicode et Le digicode

LeXav · #10

@Ebichu : Merci pour ce retour

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

nodgim · #11

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.

gwen27 · #12

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.

dhrm77 · #13

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.

nodgim · #14

Je ne comprends pas les 10 003 essais. Des essais pour fabriquer les 2000 nombres de 8 chiffres ?

nodgim · #15

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.

gwen27 · #16

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.

nodgim · #17

OK, Gwen. Et comment construit-on ce nombre ?

gwen27 · #18

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

nodgim · #19

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.

Agid1915 · #20

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.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

digicode gebtil (mais faible ?)

#0 Pub

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

digicode gentil (mais gaible ?)

#3 - 27-09-2016 17:42:05

Digicode gentil (mais faibe ?)

#4 - 27-09-2016 20:28:38

Digicode gentil (mais faibe ?)

#5 - 27-09-2016 21:48:47

digicode genyil (mais faible ?)

#6 - 28-09-2016 08:07:00

digicode gentil (mais fzible ?)

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

Digiode gentil (mais faible ?)

#8 - 28-09-2016 09:29:20

Digicode gentil (masi faible ?)

#9 - 28-09-2016 14:31:13

dogicode gentil (mais faible ?)

#10 - 28-09-2016 16:58:10

Digicode gentill (mais faible ?)

#11 - 30-09-2016 06:07:46

Digicode gentil (mais failbe ?)

#12 - 30-09-2016 07:52:02

digicode gentul (mais faible ?)

#13 - 30-09-2016 13:47:59

Digicode getnil (mais faible ?)

caduk a écrit:

#14 - 30-09-2016 14:26:32

digivode gentil (mais faible ?)

#15 - 01-10-2016 10:08:04

digicodz gentil (mais faible ?)

#16 - 01-10-2016 10:39:01

digicode gentil (mais faibme ?)

nodgim a écrit:

#17 - 01-10-2016 12:13:17

Digicode gentil (mai faible ?)

#18 - 01-10-2016 12:50:49

Digicode gentil mais faible ?)

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

Digicode genti (mais faible ?)

#20 - 01-10-2016 14:09:51

Digicode gentil (mais faaible ?)

Réponse rapide

Sujets similaires

Pied de page des forums