Système de 12 équations à 16 inconnues

Aide à la résolution d'exercices ou de problèmes dont le niveau n'entre pas dans les catégories précédentes (pour le primaire par exemple).

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Jeudi 11 Novembre 2010, 15:19

Qui pourrait m'aider à résoudre le problème suivant ? (Peut-être par un programme informatique ?)

Voici un carré de 4X4 A B C D Chacune des 16 lettres doit être remplacée par une des 16 valeurs suivantes: 125/132/134/144/154/
E F G H 156/168/176/180/190/198/200/208/209/219/243/
I J K L
M N O P On sait par ailleurs que le total des valeurs des lignes horizontales représente de haut en bas et dans l'ordre
699/729/719/689.
Le total des valeurs des lignes verticales représente de gauche à droite et dans l'ordre 719/689/729/699.

De plus les 4 additions suivantes A+B+E+I/ C+D+F+G/ H+K +L+P/ J + M +N + O ont chacune pour valeur
709.
On demande donc de compléter le tableau.

Voici ce que j'ai fait : Sur la base des 12 équations, j'ai tiré les équations suivantes : H = I + 10 J = P + 20 K = D + 10 et M = B + 10

Donc les couples BM, HI et KD sont forcément parmi les couples (134,144), (144,154), (180,190), (190,200), (198,208) et (209,219). Le couple JP est forcément parmi les couples (134,154), (156,176) et (180,200).

Merci d'avance pour ce que vous m'écrirez.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Publicité

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Jeudi 11 Novembre 2010, 15:36

Bonjour,

Il y a un gros soucis d'affichage qui est un vrai chenis ici, on retrouve la mise en page compréhensible en utilisant le pavé "citer" destiné à écrire une réponse.
Cela se rapproche beaucoup des problèmes de carré magique.
Voici un carré de 4X4
A B C D
E F G H
I J K L
M N O P
Chacune des 16 lettres doit être remplacée par une des 16 valeurs suivantes:
125/132/134/144/154/156/168/176/180/190/198/200/208/209/219/243/

On sait par ailleurs que le total des valeurs des lignes horizontales représente de haut en bas et dans l'ordre
699/729/719/689.

Le total des valeurs des lignes verticales représente de gauche à droite et dans l'ordre
719/689/729/699.

De plus les 4 additions suivantes
A + B + E + I
C + D + F + G
H + K + L + P
J + M + N + O
ont chacune pour valeur 709.
On demande donc de compléter le tableau.



Le départ me semble très valable, je ne vois pas d'autre méthode pour continuer que de tâtonner en partant des 3 couples possible pour JP.
125/132/134/144/154/156/168/176/180/190/198/200/208/209/219/243/ => 4 nombres impairs
699/729/719/689 -> tous impairs
719/689/729/699 -> tous impairs
cela peut aider...
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Samedi 13 Novembre 2010, 20:30

Merci à Framboise.
Mais impossible de résoudre ce système (trop d'inconnues). Plusieurs candidats sont intervenus. Le jury a précisé qu'effectivement, il n'était pas possible de résoudre ce problème par équations (trop d'inconnues) mais simplement par un simple examen de la grille. Finalement, ils se sont probablement rendu compte de cette impossibilité. Ils demandent simplement aux candidats de mentionner laquelle parmi ces 4 valeurs (208, 209, 219, 243) occupera un coin de la grille soit donc en A, en D , en M ou en P. Je reste tout aussi perplexe. Et vous?
Merci d'avance pour ce que vous m'écrirez.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Samedi 13 Novembre 2010, 23:55

Pour le moment je ne sais pas. Je laisse goger et parfois l'idée vient après une bonne nuit ou deux de sommeil.
Un autre point: la solution est-elle unique ou non ? En dehors d'une éventuelle symétrie, encore qu'ici je ne vois pas de symétrie possible à priori.

Chercher par un programme utilisant la force brute ?
Avec 16^16 = 18 446744 073709 551616 possibilités brutes qu'il faudrait réduire à 16! = 20 922789 888000 avec des tests ralentissant le programme il ne faut pas être pressé avec quelques 31 000 000 de secondes par an.
Avec quelques contraintes complémentaires dans le programme ? A voir.
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Dimanche 14 Novembre 2010, 07:47

Merci Framboise,

J'espère que tu auras quand même passé une bonne nuit.

La solution est unique.

Si tu as une idée, elle sera bien sûr la bienvenue.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Mardi 16 Novembre 2010, 11:40

J'ai fait quelques essais par informatique.
Pour obtenir:
689 -> 276 possibilités - pas de 154 parmi
699 -> 432 possibilités - pas d'exclu
709 -> 528 possibilités - pas d'exclu
719 -> 544 possibilités - pas d'exclu
729 -> 528 possibilités - pas d'exclu
Une attaque par force brute devient envisageable.

On doit pouvoir combiner et alléger avec:
j'ai tiré les équations suivantes : H = I + 10 J = P + 20 K = D + 10 et M = B + 10

Donc les couples BM, HI et KD sont forcément parmi les couples
(134,144), (144,154), (180,190), (190,200), (198,208) et (209,219).
Le couple JP est forcément parmi les couples
(134,154), (156,176) et (180,200).

avec l'exclusion 154 plus haut on ajoute :
N, B, J, F, P, M, O <> 154
HI ou KD = (144,154)
Le couple JP est forcément parmi les couples (156,176) et (180,200).
Dès que j'aurais un peu de temps, je vais voir cela.

Par réarrangements, on peut en tirer par ex:
N.jpg
Tri
N.jpg (8.36 Kio) Vu 1034 fois

Cela implique deux solutions symétriques sous cette forme ( sans utiiser sommes = 709 )
Je ne sais pas si cela peut servir.

reste à utiliser:
A + B + E + I
C + D + F + G
H + K + L + P
J + M + N + O
ont chacune pour valeur 709.


On pourrait soustraire 125 à chacune des variables et travailler sur un système équivalent.
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Lundi 29 Novembre 2010, 22:56

J'ai finalement utilisé la force brute avec quelques simplifications:
J'obtiens les 2 solutions exhaustives symétriques/diagonale du système équivalent.
125 156 200 208 -> 689
190 209 132 168 -> 699
176 180 144 219 -> 719
198 154 243 134 -> 729
689 699 719 729 <- total

125 190 176 198 -> 689
156 209 180 154 -> 699
200 132 144 243 -> 719
208 168 219 134 -> 729
689 699 719 729 <- total

En revenant au système initial:
180 156 154 209 => 699
219 208 134 168 => 729
144 200 243 132 => 719
176 125 198 190 => 689
719 689 729 699 <= total

132 190 168 209 => 699
243 198 134 154 => 729
144 176 219 180 => 719
200 125 208 156 => 689
719 689 729 699 <= total

Il ne reste plus qu'à vérifier pour les sommes = 709 :wink: ( c'est bon ).
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Mardi 30 Novembre 2010, 05:39

Un tout grand merci à Framboise.

Je désespérais.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Mardi 30 Novembre 2010, 08:56

Je n'oubliais pas, mais il me fallait trouver un moment. C'est un peu grâce à un de mes chats qui en s'installant au chaud sur mes genoux...
Une bonne heure pour écrire le programme et debugger, une ou 2 secondes au programme pour sortir la solution !
La méthode ( force brute ) n'est pas glorieuse; elle permet de trouver la solution.
Je ne vois toujours pas de solution astucieuse pour y parvenir. Les sommes 709 sont quasi superflues et mon programme ne les a pas utilisées. Pourrait-on les utiliser pour parvenir à la solution ?

Je me demande comment on a pu avoir l'idée et trouver une telle structure remarquable au départ. Inspiration par les carrés magiques ?

PS:
J'ai vu que c'est un peu faux en debuggant ( double comptage partiel )
On a en fait:
689 -> 213 possibilités - pas de 154 parmi
699 -> 360 possibilités - pas d'exclu
709 -> ... possibilités - pas d'exclu
719 -> 480 possibilités - pas d'exclu
729 -> 456 possibilités - pas d'exclu
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Mardi 30 Novembre 2010, 10:21

Framboise,

Ne t'inquiète pas. Merci pour tout le mal que tu t'es donné.Début février je recevrai la solution, je te la communiquerai avec commentaires s'il y en a.

Merci encore et à bientôt.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Mardi 30 Novembre 2010, 12:19

Oui. Cela m'intéresse, ma curiosité est grande. :roll:
Merci et à bientôt.

Il serait équivalent de considérer les carrés en soustrayant 125 :
sous la forme symétrique:
000 031 075 083 -> 189
065 084 007 043 -> 199
051 055 019 094 -> 219
073 029 118 009 -> 229
189 199 219 229 -> 836

ou la forme originale:
055 031 029 084 -> 199
094 083 009 043 -> 229
019 075 118 007 -> 219
051 000 073 065 -> 189
219 189 229 199 <- tot

007 065 043 084 -> 199
118 073 009 029 -> 229
019 051 094 055 -> 219
075 000 083 031 -> 189
219 189 229 199 <- tot
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Samedi 15 Janvier 2011, 20:32

A Framboise,

Voici avec une sérieuse avance, la solution au problème posé:

A=132 B=190 C= 168 D= 209 E= 243 F = 198 G = 134 H= 154 I= 144 J= 176 K= 219 L = 180 M = 200 N= 125 O= 208 P = 156


Bien à toi et encore merci.
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Samedi 15 Janvier 2011, 20:59

Et surtout un grand bravo, Framboise
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Dimanche 16 Janvier 2011, 01:04

Cela correspond exactement à la solution trouvée, c'est normal.
Ce qui aurait été intéressant est de savoir le contexte où cela a été trouvé vu que nous connaissions la solution obtenue par la force brute avec quelques astuces.

D'autres participants ont trouvé la solution ?

Merci pour l'info.
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Système de 12 équations à 16 inconnues

Messagepar Nicole 14 » Dimanche 16 Janvier 2011, 07:03

A Framboise,

Je suppose que la bonne réponse a été trouvée en jouant sur les équations. Je ne vois pas d'autre possibilité.

Le nombre de bonnes réponses, je ne le saurai que beaucoup plus tard.

Une dernière petite question Framboise, je ne suis pas informaticien, mais qu'appelles-tu "la force brute"?

Merci encore et BRAVO!
Nicole 14
Déca-utilisateur
 
Messages: 27
Inscription: Dimanche 13 Janvier 2008, 17:48
Statut actuel: Actif et salarié | Enseignant

Re: Système de 12 équations à 16 inconnues

Messagepar Valvino » Dimanche 16 Janvier 2011, 10:13

http://fr.wikipedia.org/wiki/Recherche_exhaustive

En gros c'est un algorithme tout bête qui essaye une à une toutes les possibilités et qui teste si elles sont des solutions ou non. Le problème de ce genre de techniques est qu'elles sont en général très très coûteuses en temps de calcul... Si on ne simplifie pas un peu le problème, on se retrouve avec des programmes qui doivent tourner pendant des années même pour des choses simples.

Ici Framboise a bien fait remarquer qu'il y a 16^16 = 18 446 744 073 709 551 616 possibilités... Même en comptant seulement un millième de milliseconde (une micro-seconde) par possibilités, cela correspond environ à plusieurs dizaines de milliers d'années de calculs!
Valvino
Giga-utilisateur
 
Messages: 922
Inscription: Mercredi 21 Mars 2007, 10:59
Statut actuel: Post-bac | Master

Re: Système de 12 équations à 16 inconnues

Messagepar Framboise » Dimanche 16 Janvier 2011, 10:22

"La Force brute"

C'est un terme plutôt utilisé en cryptographie pour casser un code.
Cela consiste à tester toutes les combinaisons possibles successivement afin d'obtenir le résultat.
C'est utilisé pour outrepasser un password ou par les pirates pour trouver une clef pour un programme. Cela ne peut fonctionner que si le nombre d'essais n'est pas trop grand.

Dans le problème ici, j'ai notamment limité le nombre d'essais compte tenu que l'on n'utilise pas deux fois le même nombre dans la matrice et profité de la symétrie ( -> 2 fois moins d'essais ), sinon il aurait fallu attendre très longtemps un résultat. J'ai utilisé d'autres astuces, telles que des combinaisons de 4 nombres se révélant impossibles déjà au départ et évitant de tester plus loin. Mon programme a donné tous les résultats exhaustivement en environ 1 seconde.

Dommage que l'on n'ait pas d'info sur les sources de ce problème car il ne me semble pas évident de trouver au départ une telle combinaison de nombres avec de telles propriétés ni comment une telle matrice a pu être générée pour poser un tel problème.

Je suppose que la bonne réponse a été trouvée en jouant sur les équations.
Sans recours informatique, je ne vois pas du tout comment. :roll:
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat


Retourner vers Exercices et problèmes : Autres niveaux

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité