MountyHall - La Terre des Trõlls

	Ze T-Shirt
MountyHall

Référencé sur

Nous sommes le 19° jour du Gnu du 22° cycle après Ragnarok

Bienvenue Invité

Tous les Forums

Hors Jeux - Les autres Jeux

Modérateurs de ce forum : Aghabeu, Dabihul, Grankausto, Loinvu, Madère, Mamoune, Modérateur 6, Modérateur1, Modérateur2, Modérateur3, Modérateur4, Modérateur5, Mr x, Rouletabille, Schtroumpf, TilK, VYS, Xaruth

Préfixez toujours vos titres de message du nom du jeux. Par exemple :"[Bombix]" ou "[Taupedelire]" S'il s'agit d'une présentation d'un site, n'oubliez pas d'en donner l'URL.

Attention : les liens d'affiliation et autre parrainage sont formellement interdits.

Problème mathématique

#. Message de AngelFace le 21-05-2008 à 12:50	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Un petit problème mathématique a germé dans mon esprit. Marrant, mais complexe. Comme je n'ai pas la réponse, je lance le débat ^^

L'entrée de mon parking est équipé d'un digicode. Le code est composé de 4 chiffres suivi de la lettre A.

Question 1 : combien de codes et combien de chiffres sont nécessaires pour tester toutes les possibilités.
Question 2 : comment fabriquer ces codes pour être sur de tester tous les cas.

Les réponses sont triviales : 10000 codes à tester, en incrémentation simple (de 0000A à 9999A), soit 40000 chiffres.

La porte de mon immeuble est équipé d'un digicode légèrement différent. Celui-ci n'est composé que de 4 chiffres, sans séparation. Ainsi, si on teste 12345, le code 2345 valide est accepté.

Question 1 : combien de codes et combien de chiffres sont nécessaires pour tester toutes les possibilités.

Question 2 : comment fabriquer un tel nombre.

La question 1 est un peu plus dure que précédemment. Il y a toujours 40000 codes à tester, mais un nombre unique correctement fabriqué peut réduire le nombre de chiffres. Intuitivement, je dirais qu'il est nécessaire d'avoir 10003 chiffres, et je pense qu'une démonstration par récurrence doit être réalisable.

La question 2, je sèche totalement

Des idées ?

AngelFace, qui prévoit déjà d'oublier son code...

#. Message de Laugarhraun le 21-05-2008 à 15:15	81729 - ( )
Pays: France Inscrit le : 6-09-2006 Messages: 708 (Shaï Epileptique)	Citer

oh, c'est trivial. La théorie des graphes répond à ta question de manière complète je crois. J'avais un article exactement sur ca (les combinaisons pour les digicodes), je sais plus où il est... regarde sur le site de l'ENS dans les articles des élèves, il venait peut-être de là.
edit : j'ai retrouvé ca : http://www.dma.ens.fr/culturemath/maths/pdf/combi/digicode.pdf

#. Message de TilK le 21-05-2008 à 15:35 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 6-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Quelques éléments de réponses :

Soit n le nombre la taille en caractères du digicode (ici n=4) et b le nombre de touche sur le digicode (ici b=10 : 0 1 2 3 4 5 6 7 8 9),

Alors il est facile du minorer la taille du plus petit code essayant toutes les combinaisons :
Il aura b^n+(n-1) chiffres.

En effet, il y a b^n codes possibles et le chiffre devant toutes les contenir, il doit donc contenir b^n+(n-1), les n-1 étant les caractères à la fin non associé à un code car n'ayant pas de chiffre suivants.

Prenons le cas n=2.

La meilleur façon de représenter le système est un graphe à mon avis.

Il y a b noeuds (les chiffres disponibles) et créons tous les arcs orientés possibles :
1->1
1->2
1->3
2->1
2->2
2->3
3->1
3->2
3->3

Dans ce cas ci, un combinaison (2 chiffres) est donc associé exactement à un arc.
Le problème se résume donc à trouver le plus petit chemin permettant de passer par tous les arcs. Le plus petit est garanti si on ne passe que si l'on passe une seule fois par chaque arc.

Pour b=2, c'est facile d'en exiber un :
11221 (taille 5, le plus petit)

b=3
1122331321 (taille 10, le plus petit)

b=4
11223344131424321 (taille 16, il est minimal)

b=5
11223344551314152535424321

On peut même généraliser :

112233...nn1314...1(n-2)1(n-1)2(n-1)3(n-1)4...(n-1)(n-3)(n-1)(n-2)......k+1k2k3k...(k-2)k(k-1).....5424321

Pour les cas b>2, c'est plus subtil, mais je pense que l'on peut se ramener aussi à des graphes.

#. Message de TilK le 21-05-2008 à 15:42 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 6-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Bon, je viens de lire la réponse de Laugarhraun. Ca me rassure, ma réponse est bonne et la démonstration générale va dans le bon sens.

#. Message de AngelFace le 21-05-2008 à 20:06	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Merci de votre aide précieuse. Ce qui me rassure, au contraire de Tilk, c'est qu'il y a au moins 1 personne à l'ENS aussi tourmentée que moi ^^

La réponse de Tilk est la bonne, et le lien de Laugarhraun est très complet. Par contre, quand on ne connait rien en théorie des graphes, c'est assez ardu à lire. Petit résumé pour les curieux. Je vais également utiliser le bon vocabulaire, puisque maintenant je le connais.

Tout d'abord, la taille optimisée du "mot" sans redondance est p^n+n−1, où p est le nombre de "lettres" de l'"alphabet" (1, 2, 3, 4, 5, 6, 7, 8, 9, 0), et n la longueur du code. Le nombres complet de codes est appelé "dictionnaire" (les 40000 combinaisons).

Dans mon exemple, 10^4 + 4 - 1, soit 10003. La démonstration passe par la théorie des graphes. Bien entendu, les réserves que j'avais sur le raisonnement par récurrence sont levées.

Pour le calcul du chemin, c'est plus dur. Je ne suis pas sur d'avoir tout compris dans cette démonstration, mais il me semble que l'exemple de Tilk correspond à celui qui est donné de façon générale.

Le terme précis est : Le graphe orienté est traversable, c’est-à-dire qu’il existe un circuit passant une et une seule fois par chacun de ses arcs. Or à une tel circuit correspond un mot d’exactement p^n + n − 1 lettres, qui contient tous les mots de notre dictionnaire.

Voila, petit résumé pour ceux, comme moi, qui ont du mal avec l'algèbre. Si vous comprenez les mots traversable, graphe orienté, arc, intersection, et ceux que je vous ai épargné (fortement connexe, valence paire, circuit élémentaire disjoint, pseudo-symétrique, et autres graphe eulérien), alors lisez le document de Laug'.

AngelFace, qui a du mal a comprendre sa question du coup

#. Message de Mr beaver le 22-05-2008 à 11:59	102709 - Peter The Beaver (Tomawak 24)
Pays: France Inscrit le : 30-04-2008 Messages: 36 (P'tit Gob')	Citer

Non, au niveau mathématique, c'est un peut trop complexe/chiant (pour moi)

Mais ramenons ça a un point de vue pratique

Généralement, un digicode ne change pas souvent, pas avant plusieurs année en tout cas.
Donc, en regardant bien, avec une bonne lumière, on remarque que les touche du code sont un peu moins sale et un peut plus user que celle qui ne serve pas.
MAIS sur un digicode (ceux que je connais) il est rarement utiliser 2 fois le même chiffre, et si c'est le cas, on remarque qu'il n'y en a que 3 d'usé,
Ce qui nous fait pour un digicode basique 4 chiffre (sans lettre)

un total de 24 combinaison, si on rentre une combinaison en 5 s, en 2 min au max (dernière combinaison tester), on a trouver le code
si il n'y a pas de délais entre 2 fausse manip, c'est vite fait.

si il y a un lettre, elle généralement placer soit a la fin.
Si elle est au début, ça fait le double de combinaisons (4

mais ça reste du domaine du possible, en 4 min, on a ouvert.

Apres, s'il y a 10 seconde entre chaque combinaison, il faudrat 12 minutes au grand max, chiant, mais possible.
Si il y a une durée exponentielle (première fausse combinaison : délai de 10 seconde, 2em : délai de 1 min, 3 em : délai de 4 min) c'est mort.

Méthode tester et éprouver sur 2 digicode, mais rater sur 3 autre.
Bon, j'ai pas pris en compte le problème si un chiffre se répète, mais j'ai la flegme de faire des math plus compliquer que ça.
Si vous avez la motive....

Pierrecastor, pas trop mathématicien, mais plutôt pratique et terre a terre.

#. Message de Hoor pok le 23-05-2008 à 14:04	60564 - ( )
Pays: France Inscrit le : 25-05-2005 Messages: 296 (Golem Costaud)	Citer

ca fait quand même beaucoup 10003, n'oublies pas ton code ^^

#. Message de sulgonKiller le 24-05-2008 à 02:36	82361 - SulgonKiller (Kastar 60) - The B-Team -
Pays: France (67 - Bas-Rhin) Inscrit le : 7-10-2006 Messages: 1587 (Trõll de Compèt')	Citer

sympa le doc de Laug' !

par contre il reste à construire le mot, en s'inspirant de la démo...

qui a le courage de pondre un algorithme ?

SKiller, pas de digicode chez moi

#. Message de AngelFace le 26-05-2008 à 14:22	2149 - AngelFace (Skrim 60) - Compañeros Mosca Trõlls -
Pays: France (2A - Corse-du-Sud) Inscrit le : 26-11-2002 Messages: 4231 (Djinn Tonique)	Citer

Bah j'ai regardé vite fait pour un algo (sans code derrière en plus, juste l'algo). C'est pas gagné

#. Message de Malachite le 26-05-2008 à 21:49	20848 - ( )
Pays: France Inscrit le : 15-08-2004 Messages: 860 (Shaï Epileptique)	Citer

Bon, après rassemblement d'information. C'est assez facile. Mais c'est long à expliquer pourquoi. J'essaie d'y penser et d'écrire un truc. Mais je préviens d'avance, il y aura de vrais morceaux de maths dedans (je vais lire le machin pointé par Laugarhraun. Peut-être que la réponse y est déjà :p ).

Malachite

[Pages : 1]

Pour poster une réponse sur ce Forum, vous devez d'abord vous connecter

Si vous n'êtes pas encore enregistré, vous devez d'abord vous inscrire.

Changer de Forum

[ Contact : ] - [ Heure Serveur : 07:24:19 le 25/04/2024 ] - [ Page générée en 0.016 sec. ]