une belle collection de pièces (énigme)

[Dalidou]

Bonjour,

alors voilà : une nation souhaite se doter d'une nouvelle monnaie, le coin-coin (prononcez à l'anglaise SVP).
Les ministres souhaitent doter le pays d'une collection de pièces ou billets de 6 valeurs différentes (par exemple 1, 2, 5, 10, 20, 50)
Ils se concertent pour savoir quelles valeurs choisir de façon à simplifier au maximum les dépenses de la vie courante. Dans l'idéal, il faudrait pouvoir payer des petites sommes avec un maximum de 4 pièces ou billets.

Quelles valeurs pourraient-ils choisir ?
Dans l'exemple précédent, on est assez rapidement bloqué : pour une dépense de 38 coin-coin, il faut 5 pièces ou billets (1+2+5+10+20)

Pour ma part, j'ai trouvé une collection de pièces ou billets permettant de régler avec 4 pièces ou billets, des dépenses allant jusqu'à 95 coin-coin
Saurez-vous faire mieux ?

A vos tableurs ou à vos langages de prog (moi je m'y suis pas risqué)

Je donnerai ma soluce dans quelque temps
-----

[Dalidou]

... et si vous avez une solution analytique, c'est vous le Dieu

[grosboul]

Bonjour.

Je donnerai ma soluce dans quelque temps

Quand ?

[Marcelus]

Pour ma part, j'ai trouvé une collection de pièces ou billets permettant de régler avec 4 pièces ou billets, des dépenses allant jusqu'à 95 coin-coin
Saurez-vous faire mieux ?

Bonjour,

Je présume qu'il s'agit de faire l'appoint, qu'il n'y a pas de rendu de monnaie ?

[A voir en vidéo sur Futura]

[Marcelus]

Pour le moment, avec 4 pièces ou billets, j'arrive à 44 coin-coin ... sans rendu de monnaie !

[Dalidou]

Bonjour,
oui bien sûr il y a pas de rendu de monnaie.
Je précise aussi qu'on peut prendre plusieurs fois la même pièce.
Il faut y aller pas à pas, d'abord choisir les 2 premiers chiffres, puis un 3e, un 4e, etc.
Il faut monter, mais pas trop vite et pas trop lentement.
D'abord il faut le 1 bien sûr. La 2e sera le 2, le 3 ou le 4. Vous verrez qu'avec le 4 on coince rapidement.
Donc on fait des essais : 1, 2, 7... Quand on se met à coincer (=il faudrait 5 pièces) alors on créée une nouvelle valeur.
Dans l'ex précédent, ça coince à 19 (il faudrait 1+2+2+7+7), donc la valeur suivante peut être prise à 19, ou bien un peu avant (17 ou 18).
Etc.
Ma soluce est assez incroyable. Avec mes 6 valeurs, Je passais les 60, 70 et ça continuait. A chaque chiffre j'avais une solution, et ça a monté jusqu'à 95. Tous mes autres essais n'ont pas dépassé 75.
Je la poste dans quelques jours.

[Marcelus]

Bonjour,
oui bien sûr il y a pas de rendu de monnaie.
...
Je la poste dans quelques jours.

J'en suis maintenant à 54 coin-coin ... mais je n'ai pas dis mon dernier mot !

[Marcelus]

J'en suis maintenant à 90 coin-coin ... mais je n'ai toujours pas dis mon dernier mot !

[Marcelus]

Pour ma part, j'ai trouvé une collection de pièces ou billets permettant de régler avec 4 pièces ou billets, des dépenses allant jusqu'à 95 coin-coin
Saurez-vous faire mieux ?

OUI

Les dieux, ça n'est plus ce que c'était

[Dalidou]

Bravo !
95 aussi ou encore mieux ?
C'est (un peu) l'extase quand on trouve, hein ?

[Marcelus]

J'ai mieux ... c'était d'ailleur le sens de la question : "Saurez-vous faire mieux ?"

[Marcelus]

Quand est-ce que l'on affiche les résultats ?

[Dalidou]

Pourquoi pas ce soir ?
J'ai pas l'impression que d'autres se soient intéressés au problème (merci Marcelus !)
Ma collection :
1 3 9 16 27 58
Les 10 dernières lignes :
86 = 1+27+58
87 = 1+1+27+58
88 = 3+27+58
89 = 1+3+27+58
90 = 16+16+58
91 = 1+16+16+58
92 = 9+9+16+58
93 = 3+16+16+58
94 = 9+27+58
95 = 1+9+27+58
Après, en créant un 96, je monte à 135 (mais bon, on pourrait continuer longtemps...)

[Marcelus]

Pourquoi pas ce soir ?
J'ai pas l'impression que d'autres se soient intéressés au problème (merci Marcelus !)

C'est aussi mon impression

Après, en créant un 96, je monte à 135 (mais bon, on pourrait continuer longtemps...)

Je n'ai pas compris ce que tu voulais dire



Je n'ai pas mes résultats avec moi, je repasse plus tard pour les donner.

[Dalidou]

Je voulais dire qu'en créant un septième billet avec 96 pour valeur (ok on sort de l'énoncé), on peut continuer de payer avec 4 billets des sommes allant jusqu'à 135 coin-coin : 135 = 3+9+27+96.
Alors on pourrait créer un 8e billet valant 136 et ainsi de suite... Toujours en ne payant qu'avec 4 pièces ou billets.
Bon on sort vraiment du cadre...

[Marcelus]

Juste pour te mettre un peu l'angoisse

Jusqu'à 96 :

1 - 2 - 5 - 17 - 28 - 37



je te laisse vérifier pour voir si je n'ai pas fait d'erreur

[Kondelec]

Bonjour

Je ne sais pas si j'ai bien compris la question, mais la meilleure progression possible pour minimiser le nombre de pièces serait d'adopter l'unité, puis de doubler chaque fois :
1, 2, 4, 8, 16, 32, 64, 128 etc

[Marcelus]

Je ne sais pas si j'ai bien compris la question, mais la meilleure progression possible pour minimiser le nombre de pièces serait d'adopter l'unité, puis de doubler chaque fois :
1, 2, 4, 8, 16, 32, 64, 128 etc

Donc, les 6 pièces/billets différents seraient 1, 2, 4, 8, 16, et 32.

Comment fait-on 31 en utilisant au maximum 4 pièces/billets avec les 6 valeurs ci-dessus ?

[Dalidou]

Oui, c'est tout bon Marcelus,
tu es le nouveau champion !!!
L'idéal serait d'arriver à 100, ce serait plus sympa pour poser l'énigme.
Peut-être avec un peu de temps va-t'on susciter des vocations...

[Marcelus]

L'idéal serait d'arriver à 100, ce serait plus sympa pour poser l'énigme.

Il suffit de demander :

1 - 2 - 7 - 19 - 29 - 32

Tu n'as plus qu'à vérifier

[Marcelus]

Tu ne l'avais pas vu venir celle-là

[f6exb]

T'as un algo ou c'est du cut and try ?

[Marcelus]

T'as un algo ou c'est du cut and try ?

Bonjour f6exb,

j'ai embauché une vingtaine d'Indoux qui ont taffé tout le week-end

Bien entendu, je plaisante.
Reste dans les environs, je vais y venir, mais comme c'est Dalidou qui a lancé cette énigme, je vais attendre son retour ... et je pense qu'avant de répondre à cette question, d'autres révélations seront faites ...

[oualos]

Des Indoux, le contraire d'Indurs ?

[f6exb]

Tu fais dans le Francis Blanche ?

[Marcelus]

Des Indoux, le contraire d'Indurs ?

Les Indoux, ils bossent dur, il y a pas mal d'entreprises françaises qui leur sous-traitent des tâches intellectuelles

[JPL]

Des Indiens. Les hindous sont les adepte de l’hindouisme, mais il est exact qu’on trouve parfois fautivement indous.

[Kondelec]

Donc, les 6 pièces/billets différents seraient 1, 2, 4, 8, 16, et 32.

Comment fait-on 31 en utilisant au maximum 4 pièces/billets avec les 6 valeurs ci-dessus ?

Effectivement j'avais mal compris l'énoncé...

[Marcelus]

Des Indiens. Les hindous sont les adepte de l’hindouisme, mais il est exact qu’on trouve parfois fautivement indous.

Indou => c'est ce que j'ai appris à l'école il y a longtemps, pour désigner les habitants de l'Inde, et je me souviens que le prof avait lourdement insisté sur le fait que Indien c'était en Amérique, et Indou c'était pour les habitants de l'Inde.

Par curiosité je viens de regarder. Le Robert et le site du CNRS disent : "De l'Inde, qui appartient ou se rapporte à ce pays, à ses habitants, à sa civilisation".
Pour l'orthographe, à priori les 2 sont valables, avec un "H" et sans "H"

Il existe aussi dans le Robert une autre définition décrivant les Indous/Hindous comme étant des adeptes de l'Hindouisme

Cela étant dit, je ne m'y connais absolument pas sur ce genre de sujet ... serait-ce une dénomination qui serait tombée en désuétude ... l'essentiel c'est de solutionner l'enigme de Dalidou !

[Marcelus]

Il en faut 5 : 16+8+4+2+1
Bien sur tu peux utiliser 4 pièces avec d'autres valeurs, mais ce ne sera pas aussi optimisé sur toutes les autres valeurs de 1 à n

En même temps, l'énigme spécifie qu'il ne faut utiliser que 4 pièces/billets

J'ai pris l'exemple de 31, mais si je prend celui de 63, il en faudrait 6 !!!
La solution de Dalidou permet, en respectant l'énoncée, d'aller jusqu'à 95, et j'ai moi-même proposé une solution permettant d'aller jusqu'à 96 (pour mettre un peu l'angoisse à Dalidou !) et une autre pour aller jusqu'à la barre symbolique de 100.

Le comptage binaire, vu le temps que je passe avec les µC, est la première chose qui m'ait traversé l'esprit lorsque j'ai découvert cette énigme, mais j'ai dû tout aussi vite abandonner cette piste.

EDIT : le temps que j'envoie ce message, tu avais modifié le tien ... il y a eu croisement !