![](/img/vague-bas-gauche.png) |
#1 - 22-10-2012 14:54:43
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De l'or pour mo n1000ème
C'est mon millième message bien que j'ai été un peu absent récemment. Pour fêter cela je vous propose donc un problème d'arithmétique (j'ai librement adapté pour cela un problème de la FFJM que j'avais bien aimé).
Un revendeur d'or peu scrupuleux pour personnes fortunées désirant échanger secretement de l'argent d'origine douteuse en or pratique un prix de 1000€/cm^3 (alors que le prix du marché est plus proche de 800€-850€/cm^3). Il a en sa possession des lingots des tailles suivantes: 5x7x9, 5x7x11, 5x9x11 et 7x9x11 cm.
Le revendeur a posé un écriteau sur sa porte stipulant qu'il n'échange que des multiples de 1000€ et que des lingots entiers des tailles qu'il possède.
Un jour, un riche homme d'affaires se présente pour acheter de l'or. Notre revendeur est ennuyé car bien que le l'homme d'affaires souhaite échanger un montant multiple de 1000€, il ne trouve aucune façon de fournir la quantité d'or correspondant au montant que l'homme d'affaires souhaite convertir. Cela arrive régulièrement mais, ce jour-là, il remarque que c'est la plus grande valeur multiple de 1000€ pour laquelle il se trouve dans cette situation.
Quel montant l'homme d'affaires souhaite-t-il échanger?
Evidemment pour un millième message, je compte sur de belles démonstrations et pas seulement une valeur numérique . Je donne quand même une case réponse pour valider vos raisonnements. Il faut y saisir le montant, sans espace, sans virgule et sans symbole monétaire.
Amusez-vous bien.
EDIT: En italique les modifications par rapport à l'énoncé initial suite à la remarque de titoufred.
#2 - 22-10-2012 17:41:16
- racine
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1224
dr l'or pour mon 1000ème
Si je comprends bien la question, ça voudrait dire qu'au delà d'une certaine valeur tous les entiers peuvent s'écrire comme une addition de 315, 385, 495 et 693? J'arrive pas y croire (mais je suis nul pour ce genre de problème). À moins qu'il y ait une borne supérieure du genre quantité d'or disponible sur terre?
#3 - 22-10-2012 21:44:36
- franck9525
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1935
- Lieu: 86310
e l'or pour mon 1000ème
Le problème semble sympathique et je résiste pour l'instant à la tentation de le googler. ![roll](img/smilies/roll.png)
Quel est ce nombre maximum qui ne peut être une combinaison de lingots "unités". X? / X max et X<> 315a+385b+495c+693d qqs a,b,c,d dans N
1/ Commençons donc par étudier seulement deux valeurs simples, disons 4 et 11. On note que le X est inférieur à la première série de 4 valeurs consécutives. Il suffit en effet d'ajouter la plus petite valeur ou un de ses multiples, ici 4, pour obtenir n'importe quelle valeur supérieure. ici 33 (=3*11), 34 (=2*11+3*4), 35 (=11+6*4) et 36 (=9*4) forment une série supérieure à X. X=29 dans cet exemple, soit X=(4-1)11-4
Vérifions cette intuition avec 5 et 13: X=(5-1)13-5=47 pas décomposable 48=7*5+13, 49=2*5+3*13, 50=10*5 et 51=5*5+2*13 et 52=4*13 on note que 13 n'est pas un multiple de 5. pgcd=1
Avec 6 et 15, pgcd=3. X=69? non... car seuls les multiples de 3 sont décomposables.
2/ Étudions maintenant 3 valeurs simples, disons 7, 12 et 15. Le pgcd est 1 avec 7 et 12 seules, X=(7-1)*12-7=65. Cependant, 65=2*15+5*7. On note que 12=3*4 et 15=3*5 donc permet d'obtenir tous les multiples de 3 au delà de (4-1)5-4=11 multiplications. Si X>33 alors il faut considérer 3 et 7. A suivre...
The proof of the pudding is in the eating.
#4 - 22-10-2012 23:55:58
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
fe l'or pour mon 1000ème
Le revendeur ne peut vendre qu'un nombre entier de cm^3, donc un multiple de 1000€. Il n'y a donc pas de somme maximale qu'il ne peut échanger.
#5 - 23-10-2012 00:43:33
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De ll'or pour mon 1000ème
titoufred me fait remarquer un problème avec mon énoncé. En effet lorsque j'ai adapté l'original, j'ai voulu l'attacher au réel plutôt qu'à des cm^3. Mais évidemment puisque le cm^3 vaut 1000€, n'importe quelle somme non multiple de 1000€ n'est pas atteignable, il n'y a donc pas de maximum.
Je modifie donc l'énoncé pour dire que le vendeur a posé un écriteau disant qu'il ne change que des multiples de 1000€ et que les acheteurs le savent et que l'acheteur en question se présente bien avec un multiple de 1000€.
Je suis désolé si certains ont cherché dans la mauvaise direction à cause de cette imprécision.
J'en profite pour dire que le vendeur ne vend que des lingots entiers bien sûr.
#6 - 23-10-2012 10:35:39
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
de l'ot pour mon 1000ème
@rivas: Malgré un énoncé initial moins rigoureux, j'avais bien compris le problème posé: il s'agit de trouver le plus grand nombre ne pouvant pas s'écrire comme une somme de 5x7x9, 5x7x11, 5x9x11 et 7x9x11. Ce sont mes capacités intellectuelles qui m'empêche d'accéder à la solution, pas l'énoncé de l'énigme. Mais je n'ai pas encore renoncé.
#7 - 23-10-2012 19:33:03
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
#8 - 25-10-2012 10:06:03
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De l'or por mon 1000ème
Bon, ca ressemble à un flop.
Je donne un indice ci-dessous. Dites-moi si vous souhaitez que j'ajoute du temps.
Il y a les décompositions d'entiers en facteurs premiers. J'aime bien aussi les décompositions d'entiers en sommes. C'est un domaine assez riche aussi: en somme de nombres premiers, en somme d'entiers, ...
Spoiler : Indice Si on prend 2 entiers p et q premiers entre eux, on peut écrire tous les nombres comme combinaisons de nombres positifs de ces 2 entiers à partir de pq-p-q+1. Si on autorise les multiples négatifs, on peut bien sûr écrire tous les nombres. Cela découle directement de Bezout. Le plus grand qu'on ne puisse écrire est donc pq-p-q.
Si on prend 3 entiers premiers entre eux p, q, r et que l'on forme les nombres pq, pr et qr (premiers entre eux aussi), on peut écrire tous les nombres comme combinaisons de nombres positifs de ces 3 entiers à partir de 2pqr-pq-pr-qr+1. Le plus grand qu'on ne puisse écrire est donc 2pqr-pq-pr-qr.
Si on prend 4 entiers premiers en eux comme par exemple 5, 7, 9, 11 et que l'on forme les nombres 5.7.9, 5.7.11, 5.9.11, 7.9.11, ...
Si cet indice ne suffit pas, je donnerai la valeur et du temps supplémentaire si vous le souhaitez pour le démontrer.
#9 - 25-10-2012 11:13:18
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
De l'or por mon 1000ème
Quelque chose m'échappe: le vendeur ne cède que des entiers de cm3 d'or, vu les lingots, donc que des entiers de 1000€. N'y a t il pas un autre souci dans l'énoncé ? Ne voulais tu pas dire qu'il ne vendait que des multiple de millions d'euros ?
#10 - 25-10-2012 11:32:04
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De l'or pour mon 1000me
@nodgim:
L'énoncé est équivalent à:
Quel est le plus grand nombre entier positif N que l'on ne peut PAS écrire comme somme des nombres 315, 385, 495 et et 693 affectés de coefficients entiers positifs (ou nuls)? 316 par exemple ne peut pas être écrit de cette forme.
Lorsque tu auras trouvé N, la réponse à la question est 1000*N.
Bon amusement.
#11 - 25-10-2012 11:39:26
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
dr l'or pour mon 1000ème
Ah c'est vrai, le 1000€ ne sert à rien en effet....
#12 - 26-10-2012 01:29:10
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
de l'or poir mon 1000ème
L'intérêt porté à une énigme ne se mesure pas au nombre de réponses. Ton énigme n'est pas un flop, mais sans doute trop difficile, malgré l'indice. Perso, je n'ai jamais capté la théorie des nombres et Bezout encore moins. Comme beaucoup, j'ai cherché sans succès et j'attends la solution avec impatience.
#13 - 26-10-2012 15:39:51
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De l'or pour mo n1000ème
Voici donc la réponse à cette énigme.
Soit donc p,q,r,s 4 entiers premiers entre eux. Je note N1=pqr, N2=pqs, N3=prs et N4=qrs (chacun est le produit de 3 des 4 p, q, r, s).
Le plus grand nombre que l'on ne puisse pas écrire est N=3.pqrs-pqr-pqs-prs-qrs. On peut noter que pqrs est le ppcm de pqr, pqs, prs et qrs et que le coefficient 3 vient du fait qu'on utilise 4 premiers (p,q,r,s). Voir l'indice ci-dessus avec 1 pour 2 premiers et 2 pour 3 premiers. (N=3.PPCM(N1,N2,N3,N4)-N1-N2-N3-N4)
Montrons d'abord que N ne peut s'écrire comme combinaison linéaire à coefficients entiers NATURELS de N1, ..., N4. Raisonnons par l'absurde: Si N pouvait s'écrire comme combinaison de N1, N2, N3 et N4, il existerait a, b, c, d tous positifs ou nuls tels que: 3pqrs-pqr-pqs-prs-qrs=a.pqr+b.pqs+c.prs+d.qrs (1) c'est à dire: p(3qrs-qr-qs-rs-aqr-bqs-crs)=qrs(1+d)
p était premier avec q, r et s, p divise pour 1+d et donc p <= 1+d De même q <= 1+c, r <= 1+b et s <= 1+a
Or d'après (1) 3pqrs=(a+1)pqr+(b+1)pqs+(c+1)prs+(d+1)qrs. Donc d'après ce qui précède, 3pqrs >= spqr (je n'ai pas fait exprès) + rpqs + qprs + pqrs = 4pqrs. Ce qui est impossible. N ne peut donc pas être atteint.
Il reste à montrer que c'est le plus grand. Pour cela montrons que M=N+v (avec v>0) peut être atteint.
pqr, pqs, prs et qrs sont premiers entre eux. Le théorème de (Bachet-)Bezout nous permet d'écrire qu'il existe a, b, c, d entiers RELATIFS tels que: M=a.pqr+b.pqs+c.prs+d.qrs
On peut montrer (voir lemme complémentaire à la fin) qu'on peut se ramener à: 0<=a<=(s-1), 0<=b<=(r-1), 0<=c<=(q-1) et d entier relatif quelconque (X)
On a alors M <= (s-1)pqr+(r-1)pqs+(q-1)prs+(d+1)qrs-qrs (je transforme le d.qrs restant en (d+1)qrs-qrs pour faire apparaitre -qrs). Donc M<= 3pqrs-pqr-pqs-prs-qrs+(d+1)qrs = N+(d+1)qrs
On a finalement M=N+v et M<=N+(d+1)qrs. Donc (d+1)qrs>=v>=1 donc d>=0. M peut bien s'écrire de la forme souhaitée, ce qui termine la démonstration.
Dans notre cas, p=5, q=7, r=9, s=11. N=8507, M=8508 La solution est donc 8507000€.
Je reviens sur le point (X), je l'ai placé à la fin pour ne pas surcharger le raisonnement principal. Le théorème de (Bachet-)Bezout nous permet d'écrire qu'il existe a, b, c, d entiers RELATIFS tels que: M=a.pqr+b.pqs+c.prs+d.qrs Quel que soit k entier naturel, on peut écrire: M=(a+ks)pqr+bpqs+cprs+(d-kp)qrs. Quel que soit le signe de a, on peut choisir k de façon à ce que a+ks soit bien compris entre 0 et s-1 inclusivement. On procède de même pour b et c et on se trouve donc bien dans la situation M=a'pqr+b'pqs+c'prs+d'qrs avec les conditions énoncées pour a', b' et c', d' étant bien un entier relatif.
Voila, j'espère que la prochaine énigme que je proposerai aura plus de succès. ![smile](img/smilies/smile.png) A la relecture de la solution, il est vrai qu'elle n'est pas simple. C'est quand même un joli résultat mathématique pas trop difficile à mémoriser pour le cas de 2 premiers qui répond aux problèmes de type: quelle sommes peut-on payer avec 2 types de pièces, de billets, ...
#14 - 26-10-2012 17:15:22
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
se l'or pour mon 1000ème
J'avais trouvé (a-1)(b-1) pour deux entiers, mais j'ai complètement séché pour les 4 entiers.
C'est vrai que la démonstration est assez technique et plutôt difficile sans indications. D'ailleurs, dans ta démonstration, il faudrait prouver que n'importe quel nombre supérieur à N (pas seulement M) peut s'écrire comme une combinaison linéaire des Ni à coeff entiers positifs.
Le résultat reste intéressant à connaître. J'ai appris que ça s'appelait un nombre de Frobenius.
#15 - 26-10-2012 17:29:32
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
De l'or pour mmon 1000ème
@titoufred: Tu as tout à fait raison. En fait c'est la même démonstration qui permet de montrer que l'on peut écrire tout nombre supérieur à N de cette façon. Je l'ai montré pour N+1 mais exactement le même raisonnement pour N+v donne le résultat. J'ai donc édité mon post pour y ajouter cette information.
La solution n'utilise pas de concept mathématique très poussé (Bezout) mais c'est vrai que le cheminement n'est pas évident.
Ceci étant dit, le cheminement de certains gateaux ou dénombrements que j'ai vus ici ne le sont pas non plus ![smile](img/smilies/smile.png)
Tu m'as appris un truc: je ne savais pas que ça s'appelait les nombres de Frobenius.
#16 - 26-10-2012 17:55:28
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
De l'r pour mon 1000ème
Rivas, tu aurais dû attendre avant de donner ta solution, je n'ai pas trop de temps en ce moment mais j'y réfléchissais. Ma philosophie est celle ci: si pas de réponse, pas de solution. ça devient un problème ouvert tant qu'il n'est pas résolu. ça donne un peu de sel à ce genre d'enigmes, et c'est d'autant plus valorisant pour celui qui trouve à la fin.
#17 - 26-10-2012 18:00:17
- racine
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1224
De l'or pour on 1000ème
Ça peut être une idée, mais c'est vrai que c'est désagréable d'avoir l'impression de faire un flop ( et c'est un spécialiste qui parle). Il fait juste penser à faire un petit post pour dire qu'on y pense.
#18 - 26-10-2012 18:34:57
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
De l'or pour monn 1000ème
Bah, si tu es jeune, des flops, t'en auras dans la vie. Il ne faut pas s'arrêter à ça. La question était plus difficile que Rivas n'avait cru, d'où le déficit de réponses habituelles. Laisser du temps au temps, c'est ma devise. Ici, c'est un lieu d'échanges, où on se fait plaisir. L'espace-temps de ce site est déformé, on est dans une autre dimension. Un de ces jours, si c'est Descartes ou Riemman qui interviennent, faudra pas paniquer, c'est parce qu'il auront enfin compris l'intérêt de PrisedeTête.
#19 - 26-10-2012 20:06:52
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
de l'or pour lon 1000ème
Je suis assez d'accord avec Nodgim ![smile](img/smilies/smile.png)
Au début je donnais ma solution à la fin du temps imparti quand je recevais le message me demandant de livrer ma solution . Maintenant j'attends les réactions , si le problème est intéressant il y en aura , sinon pourquoi fournir une solution que personne ne lira ?
Certains problèmes gagnent à être cachés longtemps , d'autre pas du tout . Rendre visible les messages d'une énigme ne doit entrainer systématiquement le dévoilement de sa solution .
Ce problème je l'aurais bien cherché
Vasimolo
#20 - 26-10-2012 20:44:22
- racine
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1224
De l'or pour mon 0100ème
Je pense que ça marche pour les problèmes mathématiques, un peu moins pour le reste.
#21 - 26-10-2012 21:22:22
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
eD l'or pour mon 1000ème
Euh, ...
Je suis désolé d'avoir donné la réponse trop tôt.
J'ai retiré le commentaire contrarié. La prochaine fois, si vous souhaitez du temps, n'hésitez pas à le demander, surtout que je le proposais...
|
![](/img/vague-haut-droite.png) |