Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 01-09-2017 09:21:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustraction de fractions égyyptiennes

Bonjour à tous.

Il y a de ça un certain temps, j'avais demandé de combien de façons possibles on pouvait décomposer la fraction égyptienne 1/60 en somme de 2 fractions égyptiennes.

Aujourd'hui, je demande de combien de façons possibles on peut décomposer 1/60 en différence de 2 fractions égyptiennes.

Généralité: Une fraction égyptienne 1/n possède t-elle plus de façons de la décomposer en sommes ou en différences de 2 fractions égyptiennes ?

Pour rappel, une fraction égyptienne est l'inverse d'un entier naturel, qu'on écrirait aujourd'hui 1/n.

Bonne recherche.


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 01-09-2017 11:06:59

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

souqtraction de fractions égyptiennes

j'en trouve 22
non validé par la case réponse

 #3 - 01-09-2017 11:46:05

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

soustraction de fractiins égyptiennes

C'est une bonne réponse, bravo halloduda !

Pardon de ne pas avoir complété la case réponse dans l'énoncé, ce n'est pas l'essentiel de l'énigme....

Il te reste à donner une réponse sur le cas général.

 #4 - 01-09-2017 18:26:16

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

Soustraction de fraactions égyptiennes

22 et oui, il y a plus de sommes car pour toute "fraction-somme"

1/n = 1/(n+a) + 1/(n+b)  <=>  1/n = 1/(n-a) - 1/(b-n) avec a < n < b

n=(n+a)(n+b)/(2n+a+b) 
n^2+na+nb+ab=2n^2+na+nb
soit n^2=ab

n = (n-a)(n-b)/(2n-a-b)
n^2-na-nb+ab=2n^2-na-nb
n^2=ab

Pour toute somme, on a une "fraction-différence" SAUF pour a=b=n ! soit un cas de moins...

On en a donc autant que de décompositions de n^2 pour les sommes et  une de moins pour les différences.

Pour les différences : [ Tau(n^2)-1 ] / 2
Pour les sommes :  [ Tau(n^2)-1 ] / 2  +1

 #5 - 01-09-2017 21:54:44

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

Soustracion de fractions égyptiennes

Je trouve respectivement 22 et 23 façons de décomposer 1/60 en différence et en somme de 2 fractions égyptiennes, mais je n'ai pas trouvé d'autre méthode qu'un bête tableur sad

Je pense qu'il y a exactement 1 façon de plus de décomposer une fraction égyptienne 1/n en sommes qu'en différences de 2 fractions égyptiennes, correspondant à 2 termes identiques possibles uniquement avec la somme, mais je ne peux pas le démontrer rigoureusement sad

 #6 - 02-09-2017 08:40:01

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustrcation de fractions égyptiennes

@ Gwen: presque parfait, la dernière phrase est à reprendre. Si tu voulais avoir une formule ?

@ Francky: c'est un constat correct. Entre la preuve de Gwen et la mienne, il y en a au moins 2, et sans doute davantage. C'est de l'arithmétique pure.

 #7 - 02-09-2017 19:36:40

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

soustraction de fractions égyptuennes

Bonjour,
il y a 22 façons possibles, que l'on trouve sous la forme
1 / [ (p-q)*60/p ] - 1 / [ (p-q)*60/q ] = 1/60 ou p et q sont les diviseurs de 60.
Pour chaque paire de diviseurs (p,q), on trouve donc une solution.
Pour n'obtenir chaque solution une fois, il faut prendre p et q premier entre eux.
En effet, s'ils ont un facteur n en commun, il est facile de voir que l'on peut diviser en haut et en bas par n, et que l'on retombe sur une solution déjà trouvée.
Inversement, s'ils sont premier entre eux, les dénominateurs sont 60 - 60q/p et 60p/q - 60, et l'on voit directement que ces solutions sont alors uniques (fractions irréductibles)

 #8 - 03-09-2017 09:53:05

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustracttion de fractions égyptiennes

@ Caduk: ton dénombrement est bon, ta formule aussi, en revanche, je ne vois pas très bien comment tu pourras dénombrer ça dans le cas général.

@ Gwen : Il m'a échappé en 1ère lecture que, dans ton équation de départ de la soustraction, tu poses b-n comme étant positif, ce qui n'est pas du tout une évidence (en fait c'est souvent faux). Or une fraction égyptienne est positive.

 #9 - 03-09-2017 11:32:33

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

soustraxtion de fractions égyptiennes

Pour la première question, on cherche a et b tels que 1/a - 1/b = 1/60. En posant x = 60-a, ceci devient x/(60*(60-x)) = 1/b. Il faut donc que le numérateur x de la fraction de gauche se fasse simplifier entièrement par le dénominateur.

Si x contient un facteur premier autre que 2, 3 ou 5, ce facteur ne sera contenu ni dans 60 ni dans 60-x, donc ce n'est pas possible. De plus x est plus petit que 60 : il suffit donc de tester les entiers inférieurs à 60 dont les facteurs premiers ne sont que 2, 3 ou 5, et on trouve 22 réponses.

Pour la deuxième question, si on a une décomposition sous forme de différence, c'est qu'il existe x tel que 1/n = 1/(n-x) - x/(n*(n-x)), avec le numérateur x de la dernière fraction se simplifiant entièrement.

Alors on peut aussi écrire 1/n = 1/(n+x) + x/(n*(n+x)), et le numérateur x de la dernière fraction se simplifie entièrement, car n*(n+x) = n*(n-x) + 2n*x. Donc de toute décomposition sous forme de différence, on peut déduire une décomposition sous forme de somme : il y a plus de décompositions en sommes qu'en différences.

 #10 - 03-09-2017 11:44:25

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

Sostraction de fractions égyptiennes

Bien sûr que si :

Dans l'équation de la somme, il est évident que si a ET b sont tous deux plus petits que n le résultat sera plus grand que 1/n.
Idem si ils sont plus grands, le résultat sera plus petit que 1/n.

On aborde donc la seconde équation avec la contrainte a<n<b.

Le fait de choisir a<b est purement arbitraire, j'aurais pu faire l'inverse.
Le strictement < vient du recours à la soustraction qui impose de dissocier le seul cas particulier a=n=b valable pour l'addition mais pas pour l'équivalence entre les deux équations . Les deux équations sont donc équivalentes pour tout a<b avec obligation d'avoir a<n<b

 #11 - 03-09-2017 20:57:56

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Soustraaction de fractions égyptiennes

@ Caduk: ton dénombrement est bon, ta formule aussi, en revanche, je ne vois pas très bien comment tu pourras dénombrer ça dans le cas général.

En comptant le nombre de couples de diviseurs premier entre eux, on peut montrer par récurrence la formule suivante:
[TeX]N =(3^k-3^{k-1})\sum \limits_{s \in \mathcal{P}( [\![ 1,k]\!])} \left( \left( \dfrac{2}{3} \right) ^{|s|-1} \prod \limits_{i\in s} (p_i-1) \right) + 3^{k-1}[/TeX]
Où N est le nombre de couples (n,m) de diviseurs premiers entre eux, doublons compris ( (n,m) et (m,n) ) et (1,1) compris.
Le nombre recherché est donc (N-1)/2
k est le nombre de diviseurs premiers distincts, [latex]\mathcal{P}( [\![ 1,k]\!])[/latex] est l'ensemble des sous ensembles de nombres entiers compris entre 1 et k et [latex]p_i[/latex] est la multiplicité du i-ème facteur premier.

On peut s'apercevoir que beaucoup de termes s'annulent pour les facteurs de multiplicité 1. On peut donc réduire la somme aux facteurs de multiplicité 2.

De manière plus simple, la formule se réécrit:

Pour tout les facteurs de multiplicité 1:
[TeX]N = 3^k[/TeX]
Pour 1 facteur de multiplicité [latex]p_1[/latex]:
[TeX] N =(3^k-3^{k-1})(1+p_1-1)+ 3^{k-1} = 3^k + (3^k-3^{k-1})(p_1-1)[/TeX]
Pour 2 facteurs de multiplicité [latex]p_1[/latex] et [latex]p_2[/latex]:
[TeX]N =(3^k-3^{k-1})(1+(p_1-1) + (p_2-1) + \dfrac{2}{3}(p_1-1)(p_2-1) ) + 3^{k-1} = 3^k + (3^k-3^{k-1})((p_1-1) + (p_2-1) + \dfrac{2}{3}(p_1-1)(p_2-1) )[/TeX]
Pour 3 facteurs de multiplicité [latex]p_1[/latex], [latex]p_2[/latex] et [latex]p_3[/latex]:
[TeX]N =(3^k-3^{k-1})\left[1+(p_1-1) + (p_2-1) + (p_3-1)+ \dfrac{2}{3}\left[ (p_1-1)(p_2-1) + (p_1-1)(p_3-1) + (p_2-1)(p_3-1) \right] +\dfrac{4}{9} (p_1-1)(p_2-1)(p_3-1)\right] + 3^{k-1} = 3^k + (3^k-3^{k-1})\left[(p_1-1) + (p_2-1) + (p_3-1)+ \dfrac{2}{3}\left[ (p_1-1)(p_2-1) + (p_1-1)(p_3-1) + (p_2-1)(p_3-1) \right] +\dfrac{4}{9} (p_1-1)(p_2-1)(p_3-1)\right][/TeX]
Exemple:
Pour 60 = 2^2*3*5
Il y a 3 facteurs premiers distincts
2 est de multiplicité 2. en application de la formule pour un facteur de multiplicité supérieure à 1:
N = 3^3 + (3^3-3^2)(2-1) = 27 + 18 = 45
(N-1)/2 = 22 OK

Pour 1663200 = 2^5*3^3*5^2*7*11
5 facteurs distincts
N = 3^5 + (3^5-3^4)(4 + 2 + 1 + 2*(8 + 4 + 2)/3 + 4*8/9) = 3465
(N-1)/2 = 1732

résultat qui est confirmé par le code suivant:

Code:

def egypt(n):
    c=0
    for i in range(1,n):
        if n*i%(n-i)==0:
            c+=1
    print(c)

Code:

>> egypt(1663200)
>> 1732

 #12 - 04-09-2017 12:39:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustraction de fraactions égyptiennes

@ Gwen: pardon pour ma dernière remarque, c'était une absurdité. Ton équivalence est donc entièrement correcte, et, du coup, c'est une réponse somptueuse !

 #13 - 04-09-2017 12:42:29

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustraction de fracttions égyptiennes

@ Ebichu: c'est une bonne réponse, bravo !
Pourras tu fournir la formule qui compte les différences ?

 #14 - 04-09-2017 12:57:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustraction de fractions éygptiennes

@ Caduk: et en plus, ça marche !

Sans blague, avec ta méthode, tu viens de donner une équivalence entre 2 méthodes totalement distinctes. Bien sûr, quand tu verras la solution "directe" tu te rendras compte qu'on peut faire le décompte bien plus simplement, mais il n'empêche, ça  en jette !

 #15 - 04-09-2017 13:15:24

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Soustraction de fractions égypiennes

Effectivement, je suis allé sur le sujet de la somme de fraction, et c'est un peu plus simple big_smile

 #16 - 04-09-2017 15:03:00

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Soustraction de fractins égyptiennes

Sûr !
N'empêche, il faut quand même admettre que ton cheminement a conduit à découvrir cette égalité:

"Le nombre de diviseurs du carré d'un nombre n dans l'intervalle [1,n[ est égal au nombre de couples formés par les diviseurs premiers entre eux de ce nombre."

Ce n'est pas évident. Si quelqu'un a une idée de justification.....

Sinon, merci à tous pour votre participation. Je n'ai pas grand chose à ajouter aux réponses données, celles ci ayant été au dela même de la question posée.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete