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 - 22-10-2012 14:54:43

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

se l'or pour mon 1000è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 smile.
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.



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 22-10-2012 17:41:16

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

De l'or pouur 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 : 1922
Lieu: UK

De l'or pour mo 1000ème

Le problème semble sympathique et je résiste pour l'instant à la tentation de le googler. roll

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 : 1746

de l'or oour 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 : 1105
Lieu: Jacou

De l'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 : 2710
Lieu: Luxembourg

De l'or pour mon 10000è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 : 4733

De l'or poru mon 1000ème

Il tombe mal ton 1000ème , je n'ai pas une seconde à moi mad

Bravo quand même et merci pour l'ensemble de ton œuvre lol

Vasimolo

PS : il faudra quand même que je trouve un moment pour y réfléchir smile

 #8 - 25-10-2012 10:06:03

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

De l'or poour 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 : 2953

de l'or oour 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 : 1105
Lieu: Jacou

De l'or por mon 1000ème

@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 : 2953

De l'or pour mon 10000è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 : 2710
Lieu: Luxembourg

De l'or pour mon 10000è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 : 1105
Lieu: Jacou

De l'or poru mon 1000è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
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 : 1746

De l'or por 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 : 1105
Lieu: Jacou

de l'or pour min 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

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 : 2953

De l'or pour mon 1000èm

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 mon 1000èm

Ç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 : 2953

De l'or pour on 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 : 4733

De l'or pour mon 0100ème

Je suis assez d'accord avec Nodgim smile

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é smile

Vasimolo

 #20 - 26-10-2012 20:44:22

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

De l'or pour mon 1000èè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 : 1105
Lieu: Jacou

de l'or pout 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...

 

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 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
16-12-2013 Enigmes Mathématiques
P2T
Rectangle nombre d'or par spleenface
07-02-2009 Enigmes Mathématiques
P2T
Nombre d'or. par Lylipuce54
04-05-2011 Enigmes Mathématiques
P2T
Un fil d'or et de cuivre. par 15129229518
31-08-2010 Enigmes Mathématiques
P2T
Le nombre d'or par algo36
11-11-2012 Enigmes Mathématiques
20-07-2013 Enigmes Mathématiques
P2T
Démonstration : le nombre d'or par max-le-lycéen
12-10-2008 Enigmes Mathématiques
P2T
Trouver 758 par lolek
18-09-2013 Enigmes Mathématiques
P2T
8 points alignés par Vasimolo
10-10-2009 Enigmes Mathématiques

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