Page 1 sur 1

Système de 12 équations à 16 inconnues

MessagePosté: Jeudi 11 Novembre 2010, 15:19
par Nicole 14
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.

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

MessagePosté: Jeudi 11 Novembre 2010, 15:36
par Framboise
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...

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

MessagePosté: Samedi 13 Novembre 2010, 20:30
par Nicole 14
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.

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

MessagePosté: Samedi 13 Novembre 2010, 23:55
par Framboise
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.

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

MessagePosté: Dimanche 14 Novembre 2010, 07:47
par Nicole 14
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.

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

MessagePosté: Mardi 16 Novembre 2010, 11:40
par Framboise
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 1743 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.

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

MessagePosté: Lundi 29 Novembre 2010, 22:56
par Framboise
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 ).

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

MessagePosté: Mardi 30 Novembre 2010, 05:39
par Nicole 14
Un tout grand merci à Framboise.

Je désespérais.

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

MessagePosté: Mardi 30 Novembre 2010, 08:56
par Framboise
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

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

MessagePosté: Mardi 30 Novembre 2010, 10:21
par Nicole 14
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.

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

MessagePosté: Mardi 30 Novembre 2010, 12:19
par Framboise
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

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

MessagePosté: Samedi 15 Janvier 2011, 20:32
par Nicole 14
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.

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

MessagePosté: Samedi 15 Janvier 2011, 20:59
par Nicole 14
Et surtout un grand bravo, Framboise

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

MessagePosté: Dimanche 16 Janvier 2011, 01:04
par Framboise
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.

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

MessagePosté: Dimanche 16 Janvier 2011, 07:03
par Nicole 14
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!

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

MessagePosté: Dimanche 16 Janvier 2011, 10:13
par Valvino
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!

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

MessagePosté: Dimanche 16 Janvier 2011, 10:22
par Framboise
"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: