Bonjour, notre prof de math nous a lancé un défi, et je bloque encore après plusieurs jours de recherche ...
La question est la suivante : a et b étant 2 premiers entre eux, quelle est la somme S maximale qu'on ne peut pas atteindre avec x pièces de a et y pièces de b ?
Pour l'instant, j'ai démontré que S < ab mais je ne vois pas comment trouver S !! Meme si on a envie de dire que S = ab - 1, on se rend compte qu'avec a=3 et b=8, S=13... :marteau:
Merci de me donner une piste
[Presque resolu! ]Spé - Arithmétique - ts
14 messages
- Page 1 sur 1
par minutepap0 » 26 Mai 2007, 20:44
merci pour ta réposnse rapide yos, mais quelle est la piste pour arriver à ce résultat ??
par yos » 27 Mai 2007, 19:48
Pour conjecturer le résultat ? Des essais des calculs...
Pour le démontrer c'est autre chose :
tu dois prouver deux choses :
1) que ab-a-b ne peut $être atteint (raisonne par l'absurde).
2) que tout entier n>ab-a-b peut être atteint. Tu peux partir de Bezout avec x et y entiers relatifs.
Pour le démontrer c'est autre chose :
tu dois prouver deux choses :
1) que ab-a-b ne peut $être atteint (raisonne par l'absurde).
2) que tout entier n>ab-a-b peut être atteint. Tu peux partir de Bezout avec x et y entiers relatifs.
par minutepap0 » 31 Mai 2007, 14:08
merci, c'est ok pour le premier point mais le deuxième je bloque encore, mais je vais pas me laisser faire !!
par yos » 31 Mai 2007, 15:49
Pour le premier j'avais écrit ab-a-b=ax+by donc ab=a(x+1)+b(y+1) donc a|y+1 et ça donne ab=a(x+1)+bak avec que des entiers 
ce qui est clairement impossible (second membre > premier membre).
Bon courage pour le deuxième.
Bon courage pour le deuxième.
par emdro » 05 Juin 2007, 14:24
yos a écrit:2) que tout entier n>ab-a-b peut être atteint. Tu peux partir de Bezout avec x et y entiers relatifs.
Bonjour,
intéressant comme défi!
Tu peux remplacer le "pour tout entier n" de yos par
pour k entre 1 et a (le plus petit de tes deux nombres premiers de départ),
le nombre ab-a-b+k peut-être atteint. En effet, si tu réussis à faire "ab-a-b+1", tu pourras faire "ab-a-b+(a+1)" en ajoutant une pièce de a, et ainsi de suite.
Je ne sais pas si cela t'aide.
par flight » 05 Juin 2007, 16:13
salut
s(x,y)= ax+by a et b etant 2 entiers , étant donné qu'il s'agit de l'équation d'un plan cette fonction n'a pas de maximum .
s(x,y)= ax+by a et b etant 2 entiers , étant donné qu'il s'agit de l'équation d'un plan cette fonction n'a pas de maximum .
par aviateurpilot » 05 Juin 2007, 16:50
flight a écrit:salut
s(x,y)= ax+by a et b etant 2 entiers , étant donné qu'il s'agit de l'équation d'un plan cette fonction n'a pas de maximum .
toi tu dit que
mais dans cet exo on parle de
par minutepap0 » 05 Juin 2007, 19:11
en effet, flight, z = ax + by est l'équation d'un plan lorsque x et y sont des réels qcqs, mais ici ce sont des entiers naturels, donc j'imagine qu on obtient l'ici une réunion de points... (plan intercepté par des x = k, y = k')...
merci emdro, je pense que ton idée va m'être utile, bien vu !:++:
merci emdro, je pense que ton idée va m'être utile, bien vu !:++:
par emdro » 05 Juin 2007, 22:07
Bonsoir Minutpap0,
Je crois avoir trouvé quelque chose:
Supposons aab-a-b.
On va essayer d'écrire N=ax+by. Pour cela, mon idée était de voir si a divisait N-by avec y entier de telle sorte que N-by soit positif.
J'écris donc tous les restes dans la division par a:
N-0b congru à n(0) modulo a
N-1b congru à n(1) modulo a
...
N-(a-2)b congru à n(a-2) modulo a
Tu remarques que N-(a-2)b > ab-a-b-(a-2)b = b-a > 0.
Tous ces restes n(k) et n(l) sont distincts. En effet, sinon, on aurait N-k*b congru à N-l*b modulo a, soit par différence, a divise (k-l)b et comme a et b sont premiers entre eux, a divise k-l (Gauss). Comme k et l sont entre 0 et a-2, dès qu'ils sont distincts, leur différence ne peut être multiple de a.
Jusqu'alors, on a écrit a-1 restes distincts. Il y en a a en tout (0, 1, 2, ..., a-1). De deux choses l'une:
* si un des restes est nul, disons N-k*b congru à 0 modulo a, cela signifie que N-k*b=p*a (NB p est positif car N-k*b l'est), donc on a réussi à écrire N=p*a+k*b (avec p et k positifs).
* si aucun reste n'est nul, nécessairement le suivant sera nul. C'est à dire que N-(a-1)*b est congru à 0 modulo a. (par l'absurde, sinon, deux restes seraient égaux... et on refait le raisonnement de tout à l'heure). C'est à dire que N-(a-1)*b=p*a. Mais N-(a-1)*b>-a (c'est le premier nombre de la liste qui n'était plus forcément positif). D'où p>-1 et donc p supérieur ou égal à 0.
On a encore réussi à écrire N=p*a+k*b avec p supérieur ou égal à 0 et k=a-1 lui-même supérieur à 0.
C'est ce qu'on appelle en logique un dilemme: dans les deux cas, on réussi à décomposer le nombre N en ax+by avec x et y positifs.
BILAN: Tout nombre supérieur strictement à ab-a-b peut être atteint avec des pièces de a et b.
Allié à l'idée de Yos (message numéro 6): qui dit que ab-a-b ne peut être atteint, il me semble que c'est gagné, non?
Je n'ai pas trouvé plus court!
Je crois avoir trouvé quelque chose:
Supposons a
On va essayer d'écrire N=ax+by. Pour cela, mon idée était de voir si a divisait N-by avec y entier de telle sorte que N-by soit positif.
J'écris donc tous les restes dans la division par a:
N-0b congru à n(0) modulo a
N-1b congru à n(1) modulo a
...
N-(a-2)b congru à n(a-2) modulo a
Tu remarques que N-(a-2)b > ab-a-b-(a-2)b = b-a > 0.
Tous ces restes n(k) et n(l) sont distincts. En effet, sinon, on aurait N-k*b congru à N-l*b modulo a, soit par différence, a divise (k-l)b et comme a et b sont premiers entre eux, a divise k-l (Gauss). Comme k et l sont entre 0 et a-2, dès qu'ils sont distincts, leur différence ne peut être multiple de a.
Jusqu'alors, on a écrit a-1 restes distincts. Il y en a a en tout (0, 1, 2, ..., a-1). De deux choses l'une:
* si un des restes est nul, disons N-k*b congru à 0 modulo a, cela signifie que N-k*b=p*a (NB p est positif car N-k*b l'est), donc on a réussi à écrire N=p*a+k*b (avec p et k positifs).
* si aucun reste n'est nul, nécessairement le suivant sera nul. C'est à dire que N-(a-1)*b est congru à 0 modulo a. (par l'absurde, sinon, deux restes seraient égaux... et on refait le raisonnement de tout à l'heure). C'est à dire que N-(a-1)*b=p*a. Mais N-(a-1)*b>-a (c'est le premier nombre de la liste qui n'était plus forcément positif). D'où p>-1 et donc p supérieur ou égal à 0.
On a encore réussi à écrire N=p*a+k*b avec p supérieur ou égal à 0 et k=a-1 lui-même supérieur à 0.
C'est ce qu'on appelle en logique un dilemme: dans les deux cas, on réussi à décomposer le nombre N en ax+by avec x et y positifs.
BILAN: Tout nombre supérieur strictement à ab-a-b peut être atteint avec des pièces de a et b.
Allié à l'idée de Yos (message numéro 6): qui dit que ab-a-b ne peut être atteint, il me semble que c'est gagné, non?
Je n'ai pas trouvé plus court!
par emdro » 11 Juin 2007, 18:25
Dis donc, t'es sûr que c'est bien sérieux de se coucher à 1h du mat. avec l'épreuve de philo le lendemain matin? :marteau:
Bonne chance pour le bac :happy2:
Bonne chance pour le bac :happy2:
14 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 65 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 ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :