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 - 11-07-2011 20:43:06

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

infuniment riche

Un homme possède un nombre non limité de deux types de pièces de valeurs entières premières entre elles différentes de l'unité.
Il a un problème car il ne peut PAS tout payer de manière exacte.
Il veut donner un peu plus mais ne pas s'embêter à savoir si il peut payer cette nouvelle somme.
Il décide donc de donner une somme fixe une bonne fois pour toute en plus en espérant que cela tombe sur un compte qu'il puisse payer mais se demande si c'est possible.

Pouvez-vous l'aider?

Merci.smile



Annonces sponsorisées :

Un mathématicien complet est topologiquement fermé!
  • |
  • Répondre

#0 Pub

 #2 - 12-07-2011 01:48:56

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

nIfiniment riche

Si j'ai bien compris il a une infinité de pieces dont les valeurs sont des nombre premiers. Comme il en a un infinité, il a surement des 2, des 3, des 5, des 7, etc...
Avec ces pieces il peut faire tout nombre sauf 1.
Il suffit donc d'ajouter 1 a toute somme superieure a 0, pour faire tous les nombres avec un somme de nombres premiers.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #3 - 12-07-2011 07:48:18

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

indiniment riche

Désolé je me suis mal exprimé.

Voila, cela doit être bon...


Un mathématicien complet est topologiquement fermé!

 #4 - 12-07-2011 09:07:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Infiniment richee

Juste pour être sûr: il ne on cherche X constant tel que s'il ne peut pas payer Y, il peu payer Y+X; mais s'il peut payer Y il n'est pas obligé de pouvoir payer Y+X c'est bien ça ? (De toutes façons, si ça n'est pas ça, la réponse est clairement non; par exemple s'il ne peut pas payer Y, alors (Y-X) + X n'est pas payable)

(Autrement dit, pour des pièces p1 et p2, existe-t'il un X tel que pour tout Y, Y=a.p1+b.p2 ou Y+X = a.p1+b.p2)


C'est intéressant comme problème, je vais y réfléchir.

En attendant, voilà mes premières impressions:
- c'est parfois possible: pour p1 = 2 et p2 quelconque impair; notre homme peut payer tout X pair, et tout X+1 dans le cas contraire.
- c'est parfois impossible: pour (p1;p2) = (3;5) par exemple, en effet il y a plus de sommes non payables que de sommes payables et donc aucune addition ne pourrait mettre ces éléments en correspondance.

Et surtout, LA grande remarque: quand je donne trop, moi, on me rend la monnaie smile
Et dans ce cas, quelles que soient les valeurs qu'on choisirait p1 et p2 on peut payer soit la somme exacte, soit récupérer sa monnaie tongue

 #5 - 12-07-2011 10:35:37

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 931

Infinmient riche

Quand a et b sont premiers entre eux, on sait que l'équation [latex]au+bv=c[/latex] a une infinité de solutions, mais si u>0 on a souvent v<0 et ça ne marche pas avec les pièces...

La formule pour u est [latex]u=u_0+kb[/latex] avec [latex]0\le u_0<b[/latex] , associée à [latex]v=v_0-ka[/latex].
Alors [latex]au_0<ab[/latex].
S'il décide de payer [latex]c+ab[/latex], il donne [latex]u_0[/latex] pièces de a € et [latex]v_0+a[/latex] pièces de b €, cette dernière était forcément positive.
Je propose donc qu'il majore chaque somme de la valeur [latex]ab[/latex] et tout est possible.
On doit pouvoir faire un peu mieux mais ce n'est pas la question...


Celui qui fuit les casse-tête ne vaut pas un clou.

 #6 - 12-07-2011 11:11:54

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Infiniment rice

Il y a deux types de pièces, il faut réussir à faire une somme avec ces pièces, fixée pour la suite, telle que si on l'ajoute à tout prix on puisse payer le total de manière exacte.


Un mathématicien complet est topologiquement fermé!

 #7 - 12-07-2011 12:18:55

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

infinimebt riche

Je comprends un peu mieux du coup: la question est en fait de savoir si l'ensemble des prix "impayables" est fini.

Démonstration de l'équivalence des deux questions:
Si je peux trouver une telle somme S et que l'ensemble des prix impayables n'est pas fini, alors il existe un prix impayable P > S. Du coup, P-S est un prix qui, si on lui ajoute S, est impayable; ce qui est absurde.
Réciproquement, si l'ensemble des prix impayables est fini, alors il admet un PGE noté S. Pour tout prix P>0, P+S > S donc P+S est payable

On note P et Q nos 2 valeurs de pièces.
On remarque que si je peux payer S, alors je peux payer S+P
Du coup, si j'ai P sommes payables consécutives, alors toutes les sommes supérieures sont payables elles aussi.
Le théorème de Bachet-Bézout nous indique qu'il existe a et b tels que aP+bQ = 1
a et b sont nécessairement de signes contraires, on posera a > 0 (sinon on reprend le même raisonnement en remplaçant P par Q)
Dans ce cas, X=-bPQ est payable (b est négatif)
De même, X+1 =-bPQ+1 = aP -b(P-1)Q est payable (P>1)
Plus généralement pour tout j < P, X+j = ajP -b(P-j)Q est payable
Du coup, toutes les sommes allant de X à X+p sont payables et toutes les suivantes aussi.

Notre homme a donc une solution: il résout aP+bQ = 1 via l'algorithme d'Euclide étendu, il prend le terme négatif parmi a et b et il le multiplie en valeur absolue par PQ. Tout prix ajouté à cette somme est alors payable

 #8 - 12-07-2011 13:32:46

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Infinimnet riche

Bravo à Scarta.


Un mathématicien complet est topologiquement fermé!

 #9 - 13-07-2011 00:42:24

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

Infniment riche

Avec 2 types de pièces dont les valeurs faciales n et m sont premières entre elles, le montant le plus important que l'on ne puisse pas payer est: (n-1)(m-1)-1.
Exemple: 3 et 7: on ne peut pas payer 11 et c'est le plus grand montant.

Il suffit donc qu'il choisisse (n-1)(m-1)-1 comme somme fixe à ajouter.
En effet on ne lui demandera jamais de payer 0. Et à partir de 1, la somme à payer sera toujours au moins égale à (n-1)(m-1) qui est payable avec des pièces de n et m.

J'ai eu du mal à comprendre l'énoncé. J'espère avoir compris.

Merci pour l'énigme.

 #10 - 13-07-2011 08:28:20

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

infoniment riche

Oui Rivas c'est bien ça.
J'ai fais un petit énoncé pour une fois je sais pas si c'est une bonne idée, c'est mon premier, j'espère m'améliorer.


Un mathématicien complet est topologiquement fermé!

 #11 - 13-07-2011 11:27:32

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

infiniment rivhe

Je l'ai trouvé sympa, juste un peu dur à comprendre avant ta clarification.
Mais n'hésite pas à en créer d'autres. Je trouve ça plus sympa.

Comme j'ai quelques minutes, je vais démontrer le résultat que j'ai balancé ci-dessus pour ceux que ça intéressent smile

Soit m et n premiers entre eux.
On veut montrer qu'à partir de P=(n-1)(m-1) toutes les sommes sont payables, c'est-à-dire qu'il existe a et b positifs ou nuls tels que P=an+bm.

Regardons les m valeurs P-0.n, P-1.n, P-2.n, ..., P-(m-1)n dans Zm (Z/mZ).
Puisque n et m sont premiers entre eux et qu'il y en a m consécutives, ces valeurs sont toutes différentes dans Zm donc l'une d'entre elle vaut 0, c'est-à-dire est congrue à 0 modulo m, c'est-à-dire qu'il existe b tel que cette valeur soit égale à bm. Soit a l'entier tel que P-an=bm. a est positif puisque compris par construction entre 0 et m-1. Il reste à montrer que b est aussi positif.
[TeX]P-an=nm-n-m+1-an\ge nm-n-m+1-(m-1)n \ge -m+1[/TeX]
Or P-an est divisible par m et est supérieur ou égal à -m+1. Cette valeur est donc supérieure ou égale à 0 (aucun entier entre -m+1 et 0 ne sont divisible par m).
Donc bm=P-an est supérieur ou égal à 0 donc b aussi CQFD.

On peut aussi montrer que (n-1)(m-1)-1 n'est jamais payable avec un raisonnement similaire: (n-1)(m-1)-1=(m-1)n-m et on ne peut jamais compenser le -m pour rendre le facteur de n et de m positifs.

Il y a 1 ou 2 ans, un problème plus général à été posé lors de la finale du championnat FFJM.
On choisissait 4 nombres a, b, c, d tels que:
P1=abc
P2=abd
P3=acd
P4=bcd
soient premiers entre eux.
Et il fallait trouver la plus grande somme non payable avec a, b, c et d.
Il me semble me souvenir que le résultat est 3abcd-P1-P2-P3-P4.
En posant c=d=1, on trouve 3ab-ab-ab-a-b ce qui redonne le résultat pour 2 valeurs avec la même conditions de primalité.
Avec d=1, on trouve: 2abc-ab-ac-bc avec ab, ac et bc premiers entre eux.

 #12 - 13-07-2011 18:09:28

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

nIfiniment riche

Il me semble que ça ressemble au problème de l'entier N au dela duquel on obtient toutes les sommes possibles avec 2 types de pièces. Et de mémoire, c'était qq chose comme ab-a-b si a et b sont les valeurs des pièces. Est ce bien cela ou est ce autre chose ?

 

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 : Riri, Fifi et ?

Sujets similaires

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