Serrure numérique

par **rikk** » 25 Aoû 2007, 15:30

Bonjour

J'essaie de résoudre ce problème (c'est un programme info):

une serrure est composée de 5 nombres initialisés à 0:
| 0 | 0 | 0 | 0 | 0 |

pour la débloquer, il faut que les 5 nombres soient égaux à 100,
et pour ce faire on doit appuyer sur les touches 1 à 8 du clavier:
chacune de ces touches applique une addition ou une soustraction aux
5 nombres

la touche 1 provoque:
| +5 | +2 | +1 | +7 | +5 |

la touche 2:
| +13 | -7 | -4 | +1 | +5 |

la touche 3:
| +9 | +12 | +9 | +70 | -4 |

la 4:
| -11 | +9 | 0 | +5 | -13 |

la 5:
| +4 | +17 | +12 | +9 | +24 |

la 6:
| +11 | -17 | +21 | +5 | +14 |

la 7:
| +15 | +31 | +22 | -12 | +3 |

la 8:
| +19 | -12 | +4 | +3 | -7 |

il faut donc arriver aux 5 * 100 en utilisant ou non et autant de fois que l'on
veut les 8 touches du clavier

j'ai commencé en utilisant des matrices:

et j'arrive à un système de 5 équations à 8 inconnues :rulaiz:
et je suis bloqué là..
est ce que j'ai fait fausse route ou y'a t il une autre méthode pour résoudre ça?
merci pour votre aide

par **bruce.ml** » 25 Aoû 2007, 21:24

Quand tu as plus d'inconnues que d'équations, tu peux commencer par fixer les inconnues en trop :)

par **anima** » 26 Aoû 2007, 18:47

De toutes facons, ca se voit: il y a une infinite de possibilites, et encore mieux, il y a une periode "gagnante" pour chaque combinaison de 6 touches 'fixes'.

En appuyant que sur les 5 premieres touches (soit (x6, x7, x8)=(0,0,0)), on obtient 5 equations a 5 inconnues. :happy2:

par **scelerat** » 27 Aoû 2007, 11:11

anima a écrit:De toutes facons, ca se voit: il y a une infinite de possibilites, et encore mieux, il y a une periode "gagnante" pour chaque combinaison de 6 touches 'fixes'.

En appuyant que sur les 5 premieres touches (soit (x6, x7, x8)=(0,0,0)), on obtient 5 equations a 5 inconnues. :happy2:

Et il suffit d'appuyer

fois sur la premiere touche et

fois sur la seconde ? :hum:

Moi, j'essaierais de trouver des proprietes des xi modulo 2, 3, 5, 7, etc.

par **rikk** » 27 Aoû 2007, 14:08

merci pour vos conseils,

trouver des proprietes des xi modulo 2, 3, 5, 7, etc.

je ne sais pas comment faire ça, est ce que tu aurais un petit exemple stp?

par **Help** » 28 Aoû 2007, 16:06

Il y a une méthode bête et méchante et qui ne marchera pas à tous les coups : vu que les nombres sont assez grands, tu peux supposer qu'il y a peu de chance de devoir appuyer plus de 4 (ou 9 fois) sur chaque bouton.
Cela fait 390 000 possibilités (ou 100 millions) et tu écris un programme qui les teste une par une avec de simple boucle....

Bref, ici ça marche et tu trouves 2 3 1 1 3 1 2 0 comme solution (2 fois le bouton 1, 3 fois le bouton 2, 1 fois le bouton 3...2 fois le bouton 7 et 0 fois le bouton 8)

par **rikk** » 31 Aoû 2007, 16:07

En fait je voulais éviter le brute force et trouver la solution mathématiquement,
mais étant bloqué j'ai utilisé la solution de Help.

Une solution proposée par un participant était de fixer x3,x4 et x6 par 1
et on obtient des solutions dans les naturels.

par **Flodelarab** » 31 Aoû 2007, 17:29

Ce qui est intelligent, c'est de fixer les valeurs négatives. Car il y a alors un nombre fini de positions qui atteignent 100.

On fixe la 4 (car c la seule qui fait redescendre le premier).
Si on a plusieurs possibilités, on fixe la 7 car c la seule qui fait redescendre le 4eme nombre.

etc ...

par **ninjasam** » 04 Sep 2007, 09:40

Bonjour

Il y a 2 contraintes importantes dans ce probleme qui empeche la résolution matricielle la premiere xi est entier la deuxieme xi est positif.

Si on considere juste la contrainte xi entier j'ai une tite idée. On peut essayer de faire des racourci clavier par exemple

9 = 2,8 ce qui donne 32 -19 0 4 -2
10= 2,1111 ce qui donne 33 1 0 29 25

Ce qui te donnera plusieurs façon de faire des 0 sur la colonne 3

Une fois que tu en a trouver plusieurs Tu essaye de mettre des 0 sur une autre colonne en plus de la colonne 3 dans le but de realiser un triangle. Une fois le triangle réaliser tu peut chercher à rélaiser une diagonale et ainsi avoir par exemple :

1 touche 12 0 0 0 0
1 touche 0 14 0 0 0

Pour une résolution a coup sur avec xi dans Z Il faut même 2 touche pour le premier element cad une touche a 0 0 0 0 et b 0 0 0 0 avec a et b premier entre eux
(ainsi il existe des coef c et d tel que c*a+b*d=1)

Par contre pour une résolution à coup sur dans N c'est une autre histoire. A mon avis il faut essayer de n'avoir quasiment que des raccourci de touches positifs.

Tu peux mettre quelques touches negatives (appuyer un nombre negatif de fois dessus) mais à eviter au maximum du fait que tu ne peux pas te retrouver à la fin avec des touches négatives. Par contre, il est possible de mettre des coef negatif devant les racourci si tu t'assure que le nouveau racourci est valide par rapport aux premieres touches. Par exemple
Supposon que tu ai A= 2 1 1 et B=2 1. Tu peux faire C=A -B = 1 du coup c'est valide.
Enfin sinon faut marquer clairement clairement quels sont les raccourcis "valide" (contenant que des touches positifs) et d'abord essayer d'avoir un max de racourci valide.

Bon courage

par **ninjasam** » 04 Sep 2007, 09:44

Pour la contrainte xi positif il existe l'algorithme du simplexe, il est peutêtre possible de s'en inspirer et ainsi trouver une résolution quasi formelle avec les deux contraintes xi positifs et xi entier

Serrure numérique

Serrure numérique

Autres petite idee

Qui est en ligne