Discussion :

[ram-0000]

Bonsoir,

Je cherche a savoir s'il y a des solutions à mon système d'équations et je ne sais pas par quel bout le prendre :

Je cherche au moins 2 triplets (x, y, z) et (x', y', z') tels que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
x+1/y+2/z+3 = x'+1/y'+2/z'+3
et
x+y+z = x'+y'+z'
et
x, y et z sont des entiers positifs compris entre 0 et 255

Remarque 1 : Il y a peut être plus que 2 triplets
Remarque 2 : l'écriture x' (ou y' ou z') n'a rien à voir avec la notion de dérivée.

Toute idée, piste ou solution sont les bienvenues

[Zavonen]

x+1/y+2/z+3 = x'+1/y'+2/z'+3

A quoi sert le +3 dans les deux membres ?

[Alikendarfen]

De l'utilité des parenthèses ?

Ram ! Est ce que pour : x+1/y+2/z+3 = x'+1/y'+2/z'+3

Il faut comprendre : (x+1) / (y+2) / (z+3) = (x'+1) / (y'+2) / (z'+3)

Soit : ((x+1) / (y+2)) / (z+3) = ((x'+1) / (y'+2)) / (z'+3)

?

Mais dans tous les cas, x=x', y=y', z=z' marche. Donc trouver deux solutions....

[ram-0000]

He oui, les parenthèses sont utiles mais c'était tellement clair dans ma tête que c'était sous entendu. Comme quoi, ce qui va sans dire, va mieux en se disant.

Bon, je repose le problème :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
(x+1) / (y+2) / (z+3) = (x'+1) / (y'+2) / (z'+3)
et
x+y+z = x'+y'+z'
et
x, y et z sont des entiers positifs compris dans l'intervalle [1, 255]
 
Petite précision : les 6 valeurs peuvent être égales (x=z, y=z', ...)
mais on ne doit pas avoir x=x', y=y', z=z'

Exact, il y a la solution triviale x=x', y=y', z=z', je l'avais trouvée mais elle ne me convient pas.

[Zavonen]

(x+1) / (y+2) / (z+3) = (x'+1) / (y'+2) / (z'+3)

Désolé, mais il y a encore ambigüité la division n'est pas associative
a/b/c doit il être compris comme (a/b)/c ou comme a/(b/c) ???

[ram-0000]

Désolé : dans mon idée, a/b/c = (a/b)/c = a/(b*c)

[Zavonen]

On avance, mais il y a encore qqch qui n'est pas clair.
Les quotients successifs doivent ils être nécessairement entiers ou simplement rationnels ?

[Lowelace]

Bonjour,

En fait, ton problème se ramène à :
x/(yz) = x'/(y'z') avec x,x' >= 2, y,y' >=3 et z,z'>= 4.
Et x'+y'+z' = x+y+z.

[ram-0000]

Les quotients successifs doivent ils être nécessairement entiers ou simplement rationnels ?

Aucune contrainte sur les quotients, ils peuvent être rationnels

Seul x, y, z, x', y' et z' doivent être des entiers positifs compris dans l'intervalle [1, 255]

[corentin59]

Bonsoir,

Je cherche a savoir s'il y a des solutions à mon système d'équations et je ne sais pas par quel bout le prendre :

Je cherche au moins 2 triplets (x, y, z) et (x', y', z') tels que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
x+1/y+2/z+3 = x'+1/y'+2/z'+3
et
x+y+z = x'+y'+z'
et
x, y et z sont des entiers positifs compris entre 0 et 255

Remarque 1 : Il y a peut être plus que 2 triplets
Remarque 2 : l'écriture x' (ou y' ou z') n'a rien à voir avec la notion de dérivée.

Toute idée, piste ou solution sont les bienvenues

Tu as 6 inconnues pour deux équations : cela laisse pas mal de degrés de liberté et des solutions il y en a un paquet. En faisant un bête programme itératif qui teste toutes les valeurs possibles pour x, y, z, x', y' et z' (il y en a 256 pour chacun, soit 256^6 possibilités), on obtient immédiatement plusieurs exemples de solutions.

[ram-0000]

En faisant un bête programme itératif qui teste toutes les valeurs possibles pour x, y, z, x', y' et z' (il y en a 256 pour chacun, soit 256^6 possibilités), on obtient immédiatement plusieurs exemples de solutions.

Ca, c'est l'approche "brutale" qui effectivement fonctionne et va trouver toutes les solutions (car je sais maintenant qu'il y a plusieurs et même pleins de solutions)

J'aurai souhaité une approche un peu plus "fine" et mathématique de la chose.

[Zavonen]

Le code Python suivant met environ 15 secondes
il faudrait essayer pour 200, 300
éventuellement le réécrire en C
pour des performances meilleures
A retenir pour l'algo donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# teste la condition sur les quotients
def test (t1,t2):
    return t1[0]*t2[1]*t2[2]==t2[0]*t1[1]*t1[2]
 
# détermine la liste de tous les triplets (i,j,k) de somme S avec i<=j<=k
def triplets (S):
    return [(i,j,S-i-j) for i in range(1,S/3+1) for j in range(i,2*S/3-i+1) if S-i >=2*j]
 
#compte toutes les solutions avec i+j+k=S
def sol(S):
    k=0
    L=triplets(S)
    i=len(L)
    for j in range (0,i-1):
        for k in range(j+1,i):
            if test(L[j],L[k]):
                k=k+1
                #enlever le commentaire pour voir les solutions
                #print S,L[j],L[k]
    return k
#cherche les solutions avec S<=100
#pour les avoir toutes remplacer 101 par 766
def main():
    for i in range(3,101):
        print i,sol(i)
 
if __name__ == '__main__':
    main()

[Jedai]

Cette algorithme est à oublier, pour 100 ça peut encore aller (en Haskell ça prend moins d'une seconde), mais au-delà, il y a tout simplement trop de solutions (à 200, mon programme Haskell met déjà 40s, et trouve 581_290 solutions, déjà).

Quel est l'objectif de toute façon ?

--
Jedaï

[ram-0000]

581 290 solutions ? ouah !!

Je savais déjà qu'il y en avait plusieurs mais autant, je ne pensais pas.

OK, l'objectif était de remettre en cause un algo de calcul de hash. Je trouvais et pensais (intuitivement) que cet algo était faible car trop de collisions possibles mais encore fallait il le prouver.

Au début, je voulais le faire de manière rigoureuse en mathématique mais j'avais pas les épaules assez solides.

Je pense qu'effectivement la solution pragmatique était la solution "brutale". On teste et on compte.

En tout cas merci de votre aide

[corentin59]

Je savais déjà qu'il y en avait plusieurs mais autant, je ne pensais pas.

Ben en fait, l'approche mathématique dit qu'il y a trois fois plus d'inconnues que d'équations et que de ce fait il y aura beaucoup beaucoup de solutions : tu peux t'amuser à fixer arbitrairement la valeur de 4 inconnues. Dans ce cas, il te reste deux inconnues et deux équations : tu peux résoudre facilement. Il te reste donc à compter le nombre de choix arbitraires de 4 inconnues pour avoir grosso modo le nombre de solutions (aux contraintes près).

[ram-0000]

Il aurait été aussi possible d'obtenir un système de 2 équation à 6 inconnues sans solutions possibles (pas dans ce cas avec l'énoncé que j'ai fourni, l'expérimentation l'a prouvé).

Dans ce cas alors, seul l'approche mathématique aurait prouvé qu'il n'y avait pas de solution puisque l'expérimentation qui ne trouve pas n'est pas une preuve.

[corentin59]

oui, d'accord, mais dans ce cas, quelques essais de valeurs donnent souvent une idée de la direction à prendre pour montrer rigoureusement qu'il n'y a pas de solution.

[suntsu]

Quel est le nombre de solution(s) possible(s) au système d'équations suivant:

((x+1+a) / (y+2+b)) / (z+3+c) = ((x'+1+a’) / (y'+2+b')) / (z'+3+c')
et
x + y + z = x' + y' + z'
et
a+b+c = a’+b’+c’

sachant que :

x, y, z, sont des entiers positifs compris entre 1 et 32
et
x, y, z, peuvent être égaux entre eux
et
a, b, c, sont des entier positifs compris entre 1 et 3
et
a, b, c, ne peuvent pas être égaux entre eux
et
a’, b’, c’, ont des valeurs égales à la position en ordre croisant des valeurs de x', y', z' soit :
si z' < y' < x' alors c’ < b' < a’ ou encore si z' < x' < y' alors c’ < a' < b’ etc…
et
a, b, c, ont des valeurs égales à la position en ordre croisant des valeurs de x, y, z soit :
si z < y < x alors c < b < a ou encore si z < x < y alors c < a < b etc…

Pour infos, je suis une bille en math et je ne sais vraiment pas comment faire...