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 - 02-12-2011 18:23:39

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

Donnnez la monnaie!

Bonsoir à tous.

On vous présente plusieurs piles de pièces de monnaie:
1 pile de p1 pièces d'une valeur de e1 euros chacune.
1 pile de p2 pièces d'une valeur de e2 euros chacune.
..
1 pile de pn pièces d'une valeur de en euros chacune.

On vous demande de choisir e1 e2...en de sorte que vous puissiez payer avec tout cet argent  au moins 1 fois n'importe quelle valeur entière en euros, jusqu'à un certain maximum.

Question: quelle somme maximale pourrez vous payer ?

Bon amusement



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 02-12-2011 20:47:11

nicolas647
Passionné de Prise2Tete
Enigmes résolues : 24
Messages : 96

Donne zla monnaie!

On appelle Sn la somme de l'argent des n premières piles.

Dans un but d'optimisation, on prend en = S(n-1) + 1 :

e1=1
e2=p1e1+1=p1+1
e3=p2e2+p1e1+1=p2(p1+1)+p1+1=(p1+1)(p2+2)

On fait la conjecture que en=(p1+1)...(p(n-1)+1)

On cherche à le démontrer par récurrence.
e(n+1)=Sn+1=pn*en+S(n-1)+1=pn*en+en=en(pn+1)
e(n+1)=(p1+1)...(pn+1)

On a donc établi par récurrence la valeur de en. On en déduit directement la valeur de Sn :

Sn=(p1+1)...(pn+1)-1

 #3 - 02-12-2011 21:33:37

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Donnezz la monnaie!

2^n -1 ?

 #4 - 03-12-2011 04:46:21

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

donbez la monnaie!

Je ne suis pas sur de comprendre... Y a t'il une restriction sur P1, P2, etc.. ou un rapport entre P1 et E1, entre P2 et E2, etc...?
Sinon, on peut simplement avoir une infinité P1 de pieces de 1 euros, et c'est tout.

A moins que "payer une fois" veuille dire "1 fois et une seule fois" ?
Auquel cas il suffit de prendre P1=P2=P3, etc... = 1, et E1=1, E2=2, E3=4, E4=8 (serie binaire)

Peux-tu clarifier?


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

 #5 - 03-12-2011 07:44:10

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

Doonnez la monnaie!

@dhrm: p1, p2,...sont fixés, ce n'est pas toi qui en décide. Tu ne peux agir que sur e1 e2....Et p1<>p2<>...pn.
"1 fois" signifie "au moins 1 fois".

@nicolas: Excellent! je suis étonné de la rapidité de la réponse, je m'attendais à ce que ça dure quelques jours...

 #6 - 03-12-2011 09:02:11

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

oDnnez la monnaie!

Ah ! Compris, je pensais qu'on n'utilisais qu'une pièce de chaque ...

Dans ce cas, si on utilise tout, il faut attribuer la plus grosse valeur à la pièce la plus nombreuse. et la plus petite à la pièce la moins nombreuse.

Par principe de facilité , on va dire que p1 à pn sont rangés dans l'ordre croissant.

pour pouvoir payer 1 , e1=1. On peut donc payer jusqu'à p1=e1xp1
On prends donc e2=e1xp1 +1  soit e2 = p1 + 1

On peut alors payer jusqu'à p2xe2 + p1xe1 = p2(p1 + 1) + p1

....

La somme maximum est donc définie par la suite

S(1) = p1
S(n) = S(n-1) + pn (S(n-1) + 1)
S(n) = (pn + 1) S(n-1)

La somme maximum est donc le produit des (pn+1)

Smax = (p1 +1)(p2 + 1)( p3 + 1 ) ....(pn + 1)  et il ne faut pas oublier de retrancher 1 qui ne fait office que de majorant.

Smax = [produit de 1 à n des (pn+1)] -1 avec p1<=p2<=p3....<=pn

 #7 - 03-12-2011 10:33:56

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

Donnez al monnaie!

Gwen c'est bon mais es tu sûr qu'il faille attribuer la plus grosse valeur aux pièces les plus nombreuses ?

 #8 - 03-12-2011 10:50:10

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

dpnnez la monnaie!

C'est pas faux sad , vu le résultat c'est inutile... En effet, si on change l'ordre on multiplie moins les gros nombres , mais les bornes augmentent plus vite, ce qui ne change rien au résultat.

 #9 - 03-12-2011 11:57:23

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

Donnez l monnaie!

Oui, Gwen, mais il y a une preuve cachée derrière cette propriété.

 #10 - 03-12-2011 13:19:50

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

Donenz la monnaie!

est-ce que P1, P2, P3.. pn sont superieurs ou egaux a 1?


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

 #11 - 03-12-2011 17:58:40

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

Donnze la monnaie!

@dhrm: oui.

 #12 - 03-12-2011 19:38:42

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

Donnez la monnie!

Alors je dirais:
e1= 1
e2= e1.p1+1
e3= e1.p1+e2.p2+1
e4= e1.p1+e2.p2+e3.p3+1
e5= e1.p1+e2.p2+e3.p3+e4.p4+1
e6= e1.p1+e2.p2+e3.p3+e4.p4+e5.p5+1
etc...
de cette facon je pourrais payer toutes les sommes jusqu'au maximum que je possede.
par exemple:
si:
p1=3  > e1=1
p2=2  > e2=4
p3=4  > e3=12
p4=1  > e4=60
p5=3  > e5=120
le maximum que j'ai et que je peux payer est 479.


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

 #13 - 03-12-2011 20:03:46

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

donnez la monnair!

C'est OK dhrm, mais tu dois pouvoir trouver une forme plus simple pour arriver directement à cette somme sans passer par toutes les étapes.

 #14 - 03-12-2011 20:57:17

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

Donnez l amonnaie!

On peut simplifier comme ca:
e1=1
e2=e1.(p1+1)
e3=e2.(p2+1)
e4=e3.(p3+1)
e5=e4.(p4+1)
etc...


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

 #15 - 06-12-2011 19:10:27

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

Donnez la monnaiee!

Merci aux participants.
On peut toujours établir une suite de valeurs pour les différents "e" de sorte que l'on puisse faire des sommations en n'oubliant aucune unité et sans doublon. Tout le monde a vu ça.
Quand on a réussi ça, on peut alors dire: chaque pièce, si elle est présente ou absente, donnera, associée à d'autres, une somme unique qu'on ne pourra pas remplacer par une autre pièce. les différentes valeurs possibles sont alors définies par un code dont chaque chiffre est l'un des "ei", et qui peut prendre les valeurs de 0 à ai. D'où le nombre de possiblités:
(a1+1)*(a2+1)*...(an+1)
et d'où en même temps la somme totale puisque chaque code représente une unité. Mais en ôtant le code 0, qui correspond à 0 pièces.

 

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

Mots clés des moteurs de recherche

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