Déplacement d'une fraction à l'autre

par **nodgim** » 08 Déc 2009, 07:30

Bonjour à tous.
Un petit problème de niveau troisième.
Comment passer de la fraction 283/124 à la fraction 325/266 avec pour seule opération autorisée: passer de a/b à (a+1)/(b+1) ?
La solution devra donner le nombre d'étapes.

par **ffpower** » 08 Déc 2009, 11:08

On a le droit de prendre la représentation a/b que l'on veut à chaque étape, ou faut prendre la représentation irréductible?

par **Ben314** » 08 Déc 2009, 11:19

Personnelement, j'ai considéré que l'on pouvait prendre celle qu'on veut...

par **Ben314** » 08 Déc 2009, 11:47

Si j'ai bien interprété l'énoncé, je pense que l'on peut passer de n'importe quelle fraction (>1) à une autre :
E={fractions>1}.
Sur E xRy si on peut passer de x à y avec la régle (que je comprend comme une relation d'équivalence)
alors p/q R (p-1)/(q-1) R ... R (p+q-1)/1 qui est dans Z
et 2/1 = 2k/k R (2k-k+1)/1 = (k+1)/1 pour tout k

Conclusion : je pense que j'interprète mal l'énoncé....

P.S. Je pense que la relation ne doit pas être vue comme symétrique :
p/q -> (p+1)/(q+1) mais pas le contraire.

par **Ben314** » 08 Déc 2009, 12:21

Avec "ce qu'on veut" c'est encore assez simple :
x/y = (ax)/(ay) -> (ax+b)/(ay+b) = x'/y'
en prenant a=x'-y' et b=xy'-x'y (O.K. si 1 (a+1)/(b+1) que lorsque a/b est irréductible alors il n'y a aucun choix dans les étapes et le b.p. est de savoir si partant de 283/124 on finit par tomber sur 325/266...

je part là dessus...

Ca marche pas : en une dixaine d'étapes (merci l'ordi) on tombe sur 2/1 puis sur les (k+1)/k....
Conclusion : j'ai pas compris l'énoncé.....ou bien le problème est de minimiser le nombre d'étapes ???

par **nodgim** » 08 Déc 2009, 19:43

Oui, il est autorisé de réduire la fraction, sinon ce serait impossible à résoudre.

par **nodgim** » 08 Déc 2009, 20:35

Je précise encore que si on a le rapport 4/6, on peut le réécrire 8/12 ou 2/3, ou n'importe quelle autre valeur dont le résultat est identique.

par **Ben314** » 08 Déc 2009, 20:54

Ok, mais dans le post de 11h21, il me semble que je donne une solution (certe, il me faut 283x266-124x325 étapes 'additives' ce qui en fait un peu beaucoup...)

Tu confirme que le but est de minimiser le nombre d'étapes ?

par **nodgim** » 09 Déc 2009, 07:33

On peut faire mieux que 34978 étapes. En fait, on peut le faire avec moins de 100.
Quelque chose de simple est à voir: En combien d'étapes arrive t on à une fraction réductible pour a/b quelconque irréductible ?

par **Doraki** » 09 Déc 2009, 12:33

Dans le cas général ça dépend de la factorisation en facteurs premiers de (a-b) et (a'-b') et on risque d'avoir plusieurs chemins possibles qui ne sont pas aisément comparables.

Dans le cas particulier du sujet, ce sont des nombres premiers donc c'est facile :

283/124 -> 318/159 = 2 en 35 coups
2/1 -> 5/4 = 295/236 en 3 coups
295/236 -> 325/266 en 30 coups
Soit un total de 68 coups.

Faudrait un problème avec plusieurs solutions optimales différentes, pour voir.

par **Ben314** » 09 Déc 2009, 12:41

Zut, j'avais trouvé, mais trop tard...
Je rajoute juste une remarque :
via la bijection

"l'opération autorisés" devient

et permet peut-être de mieux voir le p.b. (en tout cas, c'est comme ça que j'ai trouvé une soluce....)

Par contre, il me semble qu'il y a plus rapide (car 159 n'est pas premier) :
124/159 -> 126/159=42/53 (2 coups)
42/53 -> 53/53=1 (11 coups)
1/1 -> 4/1=236/59 (3 coups) (idem doraki)
236/59 -> 266/59 (30 coups) (idem doraki)
Soit un total de 46 coups...

par **nodgim** » 09 Déc 2009, 20:33

Ben314 a écrit:Par contre, il me semble qu'il y a plus rapide (car 159 n'est pas premier) :
124/159 -> 126/159=42/53 (2 coups)

Non, car 124/159 donne 126/161 et non 126/159.

par **Doraki** » 09 Déc 2009, 20:45

Ah oui c'est pas premier ^^' ça m'apprendra à dire n'importe quoi.

nodgim, il a changé son opération pour avoir un truc un poil plus simple mais ce qu'il a marche.

Déplacement d'une fraction à l'autre

Déplacement d'une fraction à l'autre

Qui est en ligne