Le 2011ème point...

Olympiades mathématiques, énigmes et défis
Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

Le 2011ème point...

par Waax22951 » 06 Nov 2013, 01:08

Bonjour,
J'aimerais vous faire part d'un problème qui m'a bien plu, puisque à mon niveau, il s'agit du premier vrai problème qui demandait une réflexion autre que celle des théorèmes tout fait du cours :
"Dans un repère, d est la droite d'équation :
[CENTER]5x-27y=1[/CENTER]
Le "premier point" à coordonnées entières en positives de la droite d est le point de coordonnées (11; 2)
Quel est le 2011ème point de d à coordonnées positives ?"


J'avoue que j'ai trouvé un résultat plutôt simplement, ce qui m'inquiète un peu :lol3:
Donc j'espère que nous aurons les mêmes résultats ! :we:

La bonne journée ! :zen:



nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 06 Nov 2013, 13:16

Ne t'inquiète pas, c'est normal.
J'imagine que tu as vu Bezout ? A partir de là...
Ton 2011 ème point, tu as dû le trouver quelque part vers les (50000, 10000) ?

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 06 Nov 2013, 16:24

Hum... Non, c'est quoi ? :/
Oui, j'ai trouvé les coordonnées (54281; 10052), c'est ça ? ^^

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

par chan79 » 06 Nov 2013, 16:36

Waax22951 a écrit:Hum... Non, c'est quoi ? :/
Oui, j'ai trouvé les coordonnées (54281; 10052), c'est ça ? ^^

C'est bien ça

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 06 Nov 2013, 17:44

D'accord merci ;)
Je viens de regarder sur internet l'identité de Bézout, et oui, j'ai utilisé cette méthode (enfin, quelque chose qui s'en rapproche ^^)

La bonne journée ! :zen:

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 06 Nov 2013, 21:13

En fait, je me suis renseigné un peu plus, mais le seul point commun entre ma méthode et le théorème de Bézout est que j'ai utilisé les PGCD, donc en fait il n'y a pas vraiment de rapports :/

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 07 Nov 2013, 20:13

Le theoreme de Bezout sert juste a justifier qu'une equation de ce genre admet des solutions.
L'algorithme de Bezout permet de trouver explicitement une solution.
Une fois qu'on q une solution, on peut les trouver toutes, pas besoin de Bezout pour ca.
Ici, l'algo de Bezout servirait a obtenir la solution (11,2). Mais vu que l'enonce donne deja cette solution de l'equation, pas besoin de Bezout donc..

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 07 Nov 2013, 22:49

Ne sachant pas quoi faire je me suis dis que je pourrais généraliser le problème sous la forme "" en cherchant le nombre de solutions dans , et j'ai réussi à trouver une formule permettant de trouver et , qui sont les résultats de la n-ième solution ainsi qu'un moyen de trouver le nombre de solutions, mais toutes ces formules demandent de connaître le premier couple de solution... Y aurait-il un moyen de trouver cette solution par le calcul sans utiliser d'algorithme compliqué ou une formule à rallonge ? (je dirais que oui mais j'avoue que je ne trouve pas encore ... :hein: )
Des idées ? :we:

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 08 Nov 2013, 00:02

Perso, je suis comme ffpower : je ne connais que l'algo. d'euclide pour trouver des solutions particulière (et j'ai un peu peur qu'il n'y ait que des méthodes de ce type pour trouver les solutions dans le cas général...)

D'un autre coté, l'algo d'euclide, c'est pas non plus la mer à boire...

Si tu part de ton premier exemple 5x-27y, si on applique l'algo. d'euclide "étendu", ça consiste à écrire :
27 = 5 x 0 + 1 x 27
5 = 5 x 1 + 0 x 27
Je divise 27 par 5. Le quotient est 5 et le reste est 2 : 27=5x5+2 donc
2 = 27 - 5 x 5 = (5 x 0 + 1 x 27) - 5x(5 x 1 + 0 x 27)
= -5 x 5 + 1 x 27
(étape un peu débile si on fait les calculs à la main, mais pratique si on fait faire les calcul par un ordi)
Je divise 5 par 2 : Le quotient est 2 et le reste est 1 : 5=2x2+1 donc
1 = 5 - 2 x 2 = (5 x 1 + 0 x 27) - 2x( -5 x 5 + 1 x 27)
= 11 x 5 - 2 x 27
cqfd

Essaye de le faire toi même sur un exemple avec des nombres un peu plus grands, par exemple 23 et 61.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 08 Nov 2013, 01:10

Je suis un peu fatigué donc c'est sûrement bête, mais il s'agit bien du même algorithme d'Euclide pour les pgcd, non ?
Si c'est le cas, il y a aussi la méthode de la soustraction successive qui est plus rapide si on ne veut pas se prendre la tête, non ?
Merci de vos réponses ! =D

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 08 Nov 2013, 02:41

La "méthode par soustraction" et celle "par reste de division", c'est et fait les deux mêmes...
Sauf qu'au lieu (par exemple) d'écrire que, si on divise 31 par 9, il y va 3 fois et il reste 4, ben tu va écrire 31-9=22 puis 22-9=13 puis 13-9=4.
Certes, c'est un peu moins fatiguant pour le cerveau (y'a que des soustractions à faire), mais si par hasard il y a une (ou des) divisions avec un gros quotient, ben c'est vachement plus long avec que des soustractions...
Par exemple, pour trouver le reste de la division de 357 par 11, ben perso, même de tête, je commence pas par faire 357-11 puis -11 puis -11... etc
Je commence directement par 357-330 (330=11*30) et après, effectivement, je risque de fait (éventuellement) des -11

Edit : La division par 11, c'est un mauvais exemple vu que...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 08 Nov 2013, 21:14

Hum... Je pensais que c'était à cause de la fatigue, mais en fait je ne comprend pas le raisonnement x)
Parce que, dans l'exemple, on obtient un 5 et un deux, ce qui permet de faire le lien, mais avec 23 et 61 je trouve :
61 = 23*2+15
15 = 61-23*2
15 = -2*23 - (-1)*61

15 = 7*2+1
1 = 15-7*2
1 = (-2*23 - (-1)*61)-7*2

Mais je reste bloqué, car je ne peux pas changer le 7 ou le deux... Où est ma faute ? :triste:

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 08 Nov 2013, 21:50

Au départ, tu as 61 puis 23, puis le reste de la div. de 61 par 23, c'est à dire 15.
Arrivé à ce point, tu doit diviser 23 par 15 : il y va une fois et il reste 8
(à la limite, si tu comprend parfaitement ce que tu fait, tu peut écrire qu'il y va 2 fois et qu'il reste -1 : ça gagne du temps...)

Avec 61 et 23 :

1)
61 = a
2)
23 = b
3) Je divise 61 par 23. Le quotient est 2 et le reste est 15 : 61=2x23+15 donc
15 = 61 - 2x23 = a - 2b
4) Je divise 23 par 15. Le quotient est 1 et le reste est 8 : 23=1x15+8 donc
8 = 23 - 15 = b - (a - 2b) = 3b - a
5) Je divise 15 par 8. Le quotient est 1 et le reste est 7 : 15=1x8+7 donc
7 = 15 - 8 = (a - 2b) - (3b - a) = 2a - 5b
6) Je divise 8 par 7. Le quotient est 1 et le reste est 1 : 8=1x7+1 donc
1 = 8 - 7 = (3b - a) - (2a - 5b) = 8b - 3a

conclusion : (-3)x61 + 8x23 = 1

Et, à la limite, à l'étape 5, tu pouvais écrire :
5) Je divise 15 par 8. Le quotient est 2 et le reste est -1 : 15=2x8-1 donc
1 = 2x8 - 15 = 2 x (3b - a) - (a - 2b) = 8b - 3b

De même, à partir de l'étape 3), on aurait pu écrire :
3) Je divise 61 par 23. Le quotient est 3 et le reste est -8 : 61=3x23-8 donc
8 = 3x23 - 61 = 3b - a
4) Je divise 23 par 8. Le quotient est 3 et le reste est -1 : 23=3x8-1 donc
1 = 3x8 - 23 = 3 x (3b-a) - b = 8b - 3a

(en fait, c'est peut-être plus simple à comprendre en écrivant au départ "61=a" et "23=b" pour mieux comprendre qui on ajoute avec qui)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 08 Nov 2013, 22:15

Oui c'est beaucoup plus simple comme ça ! :we:
Je pense comprendre le principe, je vais m'entrainer dès que j'aurais fini un truc ^^
Vous pensez qu'on peut transformer cet algorithme sous la forme d'une formule ou quelque chose d'autre ? :happy2:
En tout cas merci beaucoup ;)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 08 Nov 2013, 22:17

Transformer l’algorithme en une unique formule "simple", non, je pense pas qu'on puisse, mais par contre faire un programme (par exemple sous algobox), c'est très facile...

P.S. J'ai beau être vieux (et c..), je préfèrerais que tu me tutoie...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 09 Nov 2013, 00:15

Oups désolé :X
D'accord merci ;)
Et comment fait on quand c est différent de 1 ? (on le considère toujours appartenant à )
J'avoue que j'ai pas trop cherché, parce que je fais quelque chose à côté, mais je ne vois pas de méthode "logique"...
Merci ^^

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 09 Nov 2013, 00:49

Si par exemple, tu cherche une solution de 61X+23Y=17 (*),
Tu fait l'algo d'euclide pour trouver que 61x(-3) + 23x8 = 1
puis.. tu multiplie tout par 17 : 61x(-3x17)+23x(8x17) = 17
ça te donne UNE solution (qui n'est en général pas parmi les "plus petites") puis tu en déduit toutes les autres (et à la limite, tu peut chercher lesquelles ne sont "pas trop grandes")
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 09 Nov 2013, 01:03

Ben314 a écrit:Si par exemple, tu cherche une solution de 61X+23Y=17 (*),
Tu fait l'algo d'euclide pour trouver que 61x(-3) + 23x8 = 1
puis.. tu multiplie tout par 17 : 61x(-3x17)+23x(8x17) = 17
ça te donne UNE solution (qui n'est en général pas parmi les "plus petites") puis tu en déduit toutes les autres (et à la limite, tu peut chercher lesquelles ne sont "pas trop grandes")

Donc il va falloir que je trouve une méthode en fonction d'une solution... x)
Tu crois qu'il serait possible de trouver sa "place" dans l'ordre des solutions, par exemple, si on sait qu'il y a au plus 7.5 solutions (donc il y a 7 solutions entières), si on considère que les solutions sont "uniformément" réparties, on pourrait trouver le premier point ou, au moins l'emplacement de la solution par rapport aux autres. Tu penses que c'est possible ? ^^

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 09 Nov 2013, 01:38

Je ne comprend pas trop de quoi tu parle là.
Le "bon" cadre (c'est à dire le cadre dans lequel tout marche parfaitement bien) pour résoudre les équation aX+bY=c est celui des entiers relatifs (i.e. positif, nuls ou négatifs) : a,b,c sont des entiers relatif et on cherche les solutions (X,Y) parmi les couples d'entiers relatifs.
Dans ce cas, il y a soit aucune solution (par exemple 4X-6Y=7 n'a pas de solutions entières) soit une infinité de solutions.
Lorsque l'on cherche (par exemple) les solutions pour lesquelles X et Y sont des entiers naturels (i.e. positifs), je pense que le plus simple consiste souvent à commencer par chercher TOUTES les solutions dans les entiers relatifs PUIS à regarder lesquelles sont positives.

Exemple : On cherche tout les couples d'entiers positifs ou nuls (X,Y) tels que 5X+7Y=111.
On fait l'algo d'euclide.
On en déduit que a=5 et b=7 sont premiers entre eux et que 1=3a-2b.
Donc 111=333a-222b et l'équation de départ peut s'écrire aX+bY=333a-222b
soit encore b(Y+222)=a(333-X) (#)
Comme b est premier avec a et qu'il divise a(333-X), c'est qu'il divise 333-X (théorème de Gauss)
Donc 333-X=kb avec k entier relatif c'est à dire X=333-7k.
En réinjectant ce résultat dans l'équation (#) on trouve que Y+222=ka donc que Y=5k-222.
Et on termine en disant que, pour que X et Y soient positifs ou nuls, il faut que c'est à dire que .
Il y a donc 3 solutions au problème de départ.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Waax22951
Membre Relatif
Messages: 442
Enregistré le: 29 Mai 2013, 18:32
Localisation: Deux-Sèvres (79) // Paris (75)

par Waax22951 » 09 Nov 2013, 14:07

Dans mon problème de départ, je cherchais le nombre de solutions entières positives pour ax-by=c, ainsi qu'un moyen (dans un second temps) pour obtenir la "n-ième" solution entière relative de ax+by+c, en se basant sur une certaine solution, ce qui m'a paru idiot ensuite... Donc je me suis concentré sur le premier problème ^^
Donc dans mon problème de départ, il s'agissait de savoir s'il y avait des solutions réelles, le nombre de solutions s'il y en a(leur nombre est forcément fini dans les entiers positifs, puisqu'on a ax-by=c), puis de les définir en fonction du premier couple de solutions :we:
Avec l'algorithme d'Euclide, on peut avoir UNE de ces solutions, donc mon problème est que je n'aurai pas ce premier couple, et que donc je devrai définir les autres points en fonction d'un autre, quelconque, mais ça me paraît peut probable à faire...
Ou alors il me faudrait savoir la "place" de cette solution par rapport aux autres (si elle est le première, la seconde, la troisième, etc...)
Tu penses que ce serait possible ?
Je crois que j'ai déjà vu ce genre d'exemples, mais je ne me rappelle plus où ^^

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite