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 - 05-10-2018 19:12:31

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

Somme de fraction égyptiennes

Bonjour @ tous

Il s'agit dans ce problème de trouver le plus possible de fractions égyptiennes  distinctes strictement supérieures à 1/200 dont la somme est égale à 1.

Pour rappel, une fraction égyptienne est une fraction du type 1 / n, n entier naturel, dont les égyptiens antiques raffolaient, parait-il.

Ce problème est ouvert, j'ai un score établi presqu'à la main, mais il est sans doute loin d'être le meilleur.

A vos machines !



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 05-10-2018 20:12:02

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 535

somme de fractions égyptienned

Bonsoir,
Je ne suis pas sûr d'avoir bien compris le problème. Sinon, 199 fois la fraction 1/199 semble répondre à la question.

 #3 - 06-10-2018 08:13:29

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

spmme de fractions égyptiennes

Pffff....
Même pas eu le temps d'ajouter " distinct " avant la remarque.

 #4 - 06-10-2018 09:50:45

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 535

Somme de fractions égytiennes

Alors là, c'est plus difficile…

 #5 - 06-10-2018 19:10:43

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

somme de fractions égyptirnnes

Si je comprends bien l'énoncé, il faut écrire quelque chose comme : 1 = 1/2 + 1/8 + 1/9 + 1/10 + 1/15 + 1/18 + 1/24, sauf qu'au lieu de seulement 7 fractions, il faut le plus grand nombre possible de fractions, distinctes, avec des dénominateurs <200 ?

PS : peux-tu donner ton score et celui des participants, afin qu'on sache contre quoi on se bat ?

 #6 - 06-10-2018 20:04:02

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

Somme ed fractions égyptiennes

C'est bien cela, Ebichu.

Enigmatus n'a pas encore donné de résultats.

A titre de renseignement, 1/199 + 1/198 + 1/197.....arrive à 1 avec 126 termes si j'ai bonne mémoire. Bien entendu, cette façon de faire est vouée à l'échec.

Perso, j'arrive à un peu plus de la moitié de ce 126.

L'idée de cette énigme vient d'une question de cours vue sur un site voisin où on demandait de faire la preuve qu'on peut obtenir 1 comme somme d'autant de fractions égyptiennes distinctes qu'on veut, ce qui se prouve facilement.

 #7 - 07-10-2018 19:23:27

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 535

Somme de fractionns égyptiennes

Voici ma plus longue liste de dénominateurs pour l'instant (10 éléments) :

Code:

(5, 6, 8, 9, 10, 12, 15, 18, 20, 24)

Sans la limitation à 199, on peut en effet obtenir une liste aussi longue que l'on veut.
Par exemple :
1) On part de (2, 3, 6)
2) On obtient une liste de longueur triple en multipliant tous les termes par 2, 3 et 6
(4, 6, 12, 6, 9, 18, 12, 18, 36)
3) Une valeur (n) en double est remplacée par (n+1,n*(n+1)),
car 1/n = 1/(n+1) + 1/(n*(n+1))
4) S'il reste des doubles, retour en 3)
5) Retour en 2)

 #8 - 07-10-2018 21:44:42

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

Somme de fractions égypttiennes

Je tente ma chance avec :

23, 28, 33, 36, 39, 40, 44, 45, 48, 51, 52, 55, 57, 58, 60, 62, 64, 65, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 87, 88, 90, 91, 92, 93, 96, 99, 100, 102, 104, 105, 108, 110, 112, 114, 115, 116, 117, 119, 120, 126, 130, 132, 133, 135, 136, 138, 140, 143, 144, 145, 147, 150, 152, 153, 154, 155, 156, 160, 161, 162, 165, 168, 171, 174, 175, 176, 195, 196, 182, 180, 184, 189, 190, 192, 198

(87 éléments)

C'est sans doute encore un petit peu optimisable.

 #9 - 08-10-2018 08:05:45

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

Somme de fractionns égyptiennes

Très bien, Ebichu !

 #10 - 08-10-2018 16:05:42

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

Somme de fracttions égyptiennes

Je fais un poil mieux avec :

23, 27, 28, 36, 39, 40, 44, 48, 52, 54, 55, 57, 58, 60, 62, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 87, 88, 90, 91, 92, 93, 96, 99, 100, 104, 105, 108, 110, 112, 114, 115, 116, 117, 119, 120, 126, 130, 132, 133, 135, 136, 138, 140, 143, 144, 145, 147, 150, 152, 153, 154, 155, 156, 160, 161, 162, 165, 168, 170, 171, 174, 175, 176, 180, 182, 184, 187, 189, 190, 192, 195, 196, 198

soit 88 éléments. Ça devient vraiment dur de l'améliorer.

Quelques pistes pour faciliter la recherche :
* on peut s'abstenir de sélectionner les nombres qui comportent un facteur premier au moins égal à 37, car il ne sera pas possible de faire disparaître ce facteur premier du dénominateur de la somme.
* de même, inutile de jouer avec 31, 124 ou 186 (considérer les multiples de 31 pour voir cela).
* 121, 169, 125 et 128 peuvent également être oubliés.
* on peut ensuite s'intéresser aux multiples des grands nombres premiers. Par exemple, avec 29, on voit que les deux seules façons de faire disparaître 29 au dénominateur sont 1/29+1/116+1/145 ou 1/58+1/87+1/116+1/145+1/174, la deuxième étant la meilleure.
* on peut faire la même chose avec les autres grands nombres premiers, en faisant attention aux interférences qui apparaissent quand ces nombres diminuent, comme 1/187 = 1/11+1/17 qui va avoir de l'influence sur les multiples de 11 comme ceux de 17.

En tenant compte de tout ça, ça limite les possibilités.

 #11 - 08-10-2018 17:25:41

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

somme de fractions égyptienneq

OK, mais quel intérêt de faire disparaitre 1/29 en faisant la somme de 3 fractions ? Pour repartir depuis 1/20 et espérer se déployer davantage ?

 #12 - 08-10-2018 18:58:32

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

Somme de fracions égyptiennes

Ce que je dis, c'est que dans l'ensemble de nombres dont la somme des inverses vaut 1 que l'on cherche à déterminer, il y a :
* soit aucun multiple de 29
* soit uniquement 29 et 116 et 145
* soit uniquement 58 et 87 et 116 et 145 et 174
Ce sont les seules possibilités, car toutes les autres aboutiraient à une somme de la forme a/(29*b) avec 29 ne divisant pas a, donc la somme ne pourrait valoir 1.

Après, c'est à toi de voir lequel de ces 3 choix est le plus pertinent. Ce n'est clairement pas le deuxième, car le troisième aboutirait à la même somme avec deux nombres de plus, donc fournirait un meilleur ensemble. Mais entre le premier et le troisième, cela dépend. Le deuxième coûte 1/20 mais permet de placer 5 nombres ; si tous les nombres choisis étaient aussi coûteux, on aurait à la fin un ensemble de 100 nombres, ce qui est bien. J'ai donc gardé ces 5 nombres dans mon ensemble ; il est toutefois possible qu'un meilleur ensemble ne les utilise pas.

 #13 - 09-10-2018 08:11:52

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

Somme de fracctions égyptiennes

OK Ebichu.

 #14 - 12-10-2018 17:49:33

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

somme de fractipns égyptiennes

Ce temps là est au fond du seau.

Avec mes seulement 67 nombres, je suis loin du record d'Ebichu avec son 88. Le challenge est ouvert, avis aux amateurs !

Je donne ici mon algo, pour que vous ne le reproduisiez pas.

1) Lister au préalable, pour tout n, toutes les paires (a,b) telles que 1/n = 1/a + 1/b avec a et b distincts. ça se fait facilement en se servant des diviseurs de n² < n.

2) En commençant par 1/2 + 1/3 + 1/6, remplacer la plus grosse fraction par la paire disponible. Si plusieurs choix, choisir celle avec I a - b I minimum.

3) Recommencer en 2)

A la fin, on peut améliorer en choisissant 1 / n = 1 / 2n + 1 / 2n si 1/ 2n libre et 1 / 2n remplaçable par une paire (a,b) libre également.

11
12
15
20
28
35
36
39
40
44
48
52
55
56
60
63
64
65
66
70
75
78
80
81
84
88
90
91
96
99
100
102
104
105
108
110
112
117
119
120
126
130
135
136
143
144
147
150
153
154
156
160
162
168
170
171
175
176
180
182
187
189
190
192
195
196
198

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

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