une belle collection de pièces (énigme)

[Kondelec]

En fait j'avais compris qu'il ne fallait utiliser qu'un exemplaire de chaque pièce, mais ce n'est pas le cas, ce qui change tout
-----

[Marcelus]

En fait j'avais compris qu'il ne fallait utiliser qu'un exemplaire de chaque pièce, mais ce n'est pas le cas, ce qui change tout

C'est pas grâve !

Si le coeur t'en dit, tu peux essayer.
Actuellement, la meilleure solution publiée permet d'aller jusqu'à 100.

D'après une théorie que j'ai bidouillé, on devrait peut-être pouvoir faire un petit peu mieux

[Dalidou]

Ah, ça s'emballe un peu c'est bien !
Pas de problème Marcellus, je suis pas du genre à "angoisser".
J'ai commencé à programmer un testeur, au moins ça prendra qu'une minute pour tester une combinaison. Je testerai ta V2 avec.
Et je trouverai peut-être mieux...!

[Marcelus]

Ah, ça s'emballe un peu c'est bien !
Pas de problème Marcellus, je suis pas du genre à "angoisser".
J'ai commencé à programmer un testeur, au moins ça prendra qu'une minute pour tester une combinaison. Je testerai ta V2 avec.
Et je trouverai peut-être mieux...!

Et ... bon chance !

[Marcelus]

J'ai travaillé des équations très complexes et j'en arrive à la conclusion que le nombre maximum théorique que l'on devrait pouvoir obtenir ne dépassera pas :


Factorielle (nombre de billets différents) + (nombre de billets différents)^2
---------------------------------------------------------------------------------------- = (720 + 36) / 7 = 108

Nombre de billets différents + 1

Il s'agit du maximum théorique, rien ne garantie que l'on pourra atteindre cette valeur

Tout ceci est du pipo !


Et ... bon chance !

[Dalidou]

C'est bon j'ai un 100 aussi :
1 3 9 14 37 44
enfin sauf erreur sur mon testeur...

[Dalidou]

1 3 9 14 39 46 -> 104 !
On se rapproche du "mur de Marcelus"...

[Marcelus]

1 - 3 - 7 - 19 - 29 - 46

107

[Dalidou]

argggg, tu m'as grillé (bon j'en étais pas encore à 1 3 7)
reste plus qu'à trouver le 108, si c'est bien la limite, mais bon je bosse donc pas trop le temps...
Je te fais confiance pour le calcul complexe, je n'imagine même pas comment tu as procédé.

[Marcelus]

je n'imagine même pas comment tu as procédé.

Ca je te le confirme !

[Dalidou]

Marcelus,
tu as pu balayer le spectre des combinaisons ?
Moi j'ai un testeur, ça me prend 1 seconde pour changer un des chiffres mais il y a tellement de possibilités...!
Sinon, on en restera là.
Tu auras le record officiel, mais il restera un doute
Merci à toi en tout cas.

[Marcelus]

Je vais expliquer la formule que j'ai donné au post#35

Pour comprendre cette formule, il suffit de sélectionner tout le texte du post#35 avec la souris ... et là ça devrait être plus clair

[Dalidou]

Hello,
pas compris ton dernier post Marcellus.
Le doute que j'évoquais ne concernait pas ta formule, je veux bien l'accepter et considérer que 108 est un maximum. Mais du coup avec ton record à 107, il y a un doute sur le fait qu'on puisse accéder à 108 ou pas...

Au fait j'ai égalé ton record : 1 3 10 15 37 48 -> 107

[Marcelus]

Bonjour Dalidou,

fait ce que je te dis et tu vas comprendre :

va sur le post#35, et sélectionne avec ta souris la TOTALITE du texte du post.

J'attend ta réponse pour publier la suite ...

[Marcelus]

En attendant que tu répondes sur le message précédent, comme je ne peux pas te laisser égaliser sans réagir, j'annonce un autre 107 :

1 - 3 - 11 - 18 - 38 - 44



Et ... bon chance !

[Dalidou]

Aaaaah !
Alors en toute franchise, je me disais : c'est soit un génie, soit du bluff.
Dans ta formule, il n'y avait pas la variable "nombre de billets que j'additionne" (4)
Et puis je me rendais compte que 108 était un maximum crédible, donc...
Au final, je récapitule :
1) je suis l'inventeur du problème
2) je suis le co-détenteur du record
3) ta formule vaut queutchi
Na !

[Marcelus]

Oh là ! Il va se calmer l'ancien !
Bien entendu, je plaisante

3) ta formule vaut queutchi
Na !

Bouge pas, je vais revenir sur ta théorie ... ça risque de ne pas être triste !

Au final, je récapitule :
1) je suis l'inventeur du problème
2) je suis le co-détenteur du record

Pour le 1, c'est vrai, et je t'en félicite, je me suis bien amusé et on a bien rigolé

Pour le 2, t'as vu ça où ???
J'ose espérer que tu plaisantes ...

1 - 4 - 9 - 16 - 38 - 49

et

1 - 5 - 8 - 27 - 29 - 44

Pour ceux qui se demanderaient, ça permet d'arriver à 108, ce qui explique que j'ai annoncé cette valeur il y a une semaine, et que j'ai voulu voir s'il y en avait qui suivaient en bidouillant volontairement une formule qui soit visiblement fausse, car comme l'a fait remarquer Dalidou, le nombre de billets que l'on peut utiliser n'est pas dans la formule, ce qui pose un sérieux et très évident problème, même sans rien connaitre aux maths.
D'ailleur, c'était écrit ... mais bon ... j'ai dû me tromper de couleur sur cette partie !



Je ne pense pas que l'on puisse aller au delà de 108, et cette fois-ci je le dis sérieusement.
Je n'irais pas parier 1 million, mais une pizza serait envisageable.

Je ne peux pas actuellement démonter que l'on ne peux pas aller au-dessus de 108, mais je pense que je pourrais peut-être y arriver, en partant de la méthode que j'ai utilisé (je vais y revenir) et en utilisant certains des résultats obtenus ... mais je ne vais pas essayer, car trop long et pas sûr d'y arriver.


A suivre, une petite analyse personnelle du problème et de la solution ...

[vgondr98]

Bonjour, j'ai fait un programme testant toute les possibilités :
1 - 4 - 9 - 16 - 38 - 49
108

[Marcelus]

J'ai dis que j'allais revenir sur ta théorie ... c'est maintenant :

déjà, j'ai bien regardé pour voir s'il n'y avait pas un message caché, indiquant que la théorie exposée était en fait destinée à tromper l'adversaire, mais queutchi !

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.

Pour le premier chiffre, on est d'accord, car pour faire 1 ... il faut 1 et rien d'autre.

Pour le deuxième chiffre, ça part en vrille : pourquoi est-ce que ça devrait être le 2, le 3 ou le 4 ?
Ca, c'est de la discrimination, et par les temps qui courent, c'est un coup à se prendre un procès par le 5, qui aura vite fait de démontrer que le fait de le choisir comme 2ème valeur n'empêche pas de pouvoir réaliser tous les totaux inférieurs (2, 3 ou 4). En revanche, le 6 ne peux pas en dire autant.

Quand à la théorie visant à dire qu'il faut d'abord choisir les 2 premiers, puis le troisième, puis le quatrième, ...etc., comme il était dit dans Kaamelott : "ça pue du cul ... mais violent !"

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.

Rien de plus à ajouter que ce que j'ai dit !



Cela dit, je te chambre un peu, mais bon, comme je l'ai déjà dit, je me suis bien amusé et j'ai bien rigolé, et même si ton raisonnement de départ n'était pas bon, j'imagine que tu as été capable de le remettre en question lorsque tu as su que l'on pouvait aller au-delà de 95, sans quoi tu n'aurais jamais pu ESSAYER d'égaliser le record, qui est à 108 depuis une semaine !

[Marcelus]

Bonjour, j'ai fait un programme testant toute les possibilités :
1 - 4 - 9 - 16 - 38 - 49
108

Effectivement, c'est bien l'une des 2 solutions données dans le post#47

[Marcelus]

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

Je vais maintenant un peu parler de la méthode que j'ai employé, et je cite f6exb comme ça il aura une notification, vu qu'il attend depuis un moment et que ça c'est un peu éternisé.


Bon au départ, j'ai fait un peu comme tout le monde, j'ai essayer de réfléchir à une approche mathématique, avec en ligne de mire le comptage binaire, mais très vite j'ai compris que ça ne mènerait à rien, et surtout pas au 95.

N'étant pas particulièrement doué en mathématiques, j'ai rapidement abandonné cette voie, pour me rabattre sur de la programmation.
L'algorithme d'un tel programme est très simple dans sa version basique, cependant mon problème est qu'actuellement je ne dispose pas de mon matériel habituel, j'ai un notebook équipé de ce qu'il y avait de moins puissant comme processeur, avec un compilateur du siècle dernier, et des PIC 8 bits, et vu la puissance du notebook et l'efficacité du compilateir installé dessus, j'ai sérieusement envisagé de programmer un PIC !


N'ayant pas un I9 ou même un I7 à disposition, impossible de faire tourner 6 boucles imbriquées pour tester toutes les valeurs possibles, tout du moins pas si je voulais que ma "machine" me donne un résultat avant la fin de la décénie (et je n'exagère pas du tout)

Il a donc fallu réduire le champ de recherche, sans pour autant risquer de passer à coté du résultat.
La grosse difficultée pour moi a été de trouver des astuces pour réduire le nombre de boucles.

Réduire le champ de recherche :

- Pour le premier nombre, il faut choisir le 1, car c'est le seul qui permet de pouvoir payer un montant de 1 coin-coin (1 boucle imbriquée en moins)

- Pour le deuxième nombre, ça ne peut pas être le 1, qui est déjà là, et ça ne peux pas non plus être supérieur à 5, sinon il serait impossible de payer 5 coin-coin

- Pour le 3ème nombre, vu qu'au minimum il y aura un 1 et un 2 et que ces 2 valeurs pourraient assurées par les 2 premiers billets, alors le troisième commencera à partir de 3. Idem pour le 4ème qui commencera à partir de 4, ...etc.

- Concernant la valeur maxi que peut prendre le 3ème nombre, vu que le 2ème vaudra au maximum 5, et que 4 x 5 fait 20, le 3ème nombre vaudra au maximum 21, car s'il vallait 22, il serait impossible de payer 21 coin-coin

- Etc...

- Il a aussi fallu que j'optimise le calcul des résultats et leur gestion



Pour info, après de très nombreux essais, le "monstre" aura tourné plein pot durant plus de 12H pour sortir les résultats à 108



S'il y a des questions, je reste dans le coin (coin !)

[vgondr98]

Pour la majoration des boucles, j'ai utilisé au départ les valeurs :
1 - 5 - 21 - 85 - 341 -1365
Cela correspond à 4 fois le nombre précédent + 1.
Comme c'était trop long, j'ai ensuite utilisé les valeurs :
1 - 5 - 17 - 57 - 189 - 625 qui correspondent à 3 fois le nombre n - 1 + 1 fois le nombre n - 2.
C'était encore trop long donc j'ai utilisé les valeurs :
1 - 5 - 13 - 37 - 101 - 277 qui correspondent à 2 fois le nombre n - 1 + 2 fois le nombre n - 2.
C'était encore trop long donc j'ai utilisé les valeurs :
1 - 5 - 9 - 25 - 53 - 129 qui correspondent à 1 fois le nombre n-1 + 3 fois le nombre n - 2.
Avec ces valeurs, c'était assez rapide (2 minutes de calcul).
Je pense que le raisonnement est correcte.

[Dalidou]

Bonjour à tous (enfin les quelques "pelés" égarés sur ce fil),

Oui je suis sans doute allé trop vite (par exemple en disant que 1 – 4 etc. n'était pas possible).
Il faut dire que je n'avais qu'un tableur (et pas beaucoup de temps) à ma disposition pour tester une à une chaque combinaison (comment faire 1, comment faire 2, etc jusqu'à 90 ou plus)

Quand j'ai pu me bricoler un testeur rapide, j'ai constaté mes erreurs et pu visualiser les progrès à faire. Avec ce système et sans programme, eh bien SI, il faut choisir la 2e valeur, puis la 3e, et ainsi de suite.

De ton côté Marcelus, tu as caché dès le départ des informations (ton programme et le fait que tu as trouvé des 108 comme chiffre maximal), tout en disséminant des fausses (ta super formule), ce qui n'était pas très cool vu le temps que j'ai perdu à faire mes tests. Ce n'est pas vraiment une démarche collaborative et «*scientifique*». Si tu as bien ri de te moquer de moi, tant mieux pour toi. Je ne sais pas si c'est le bon forum pour ça, je te laisse y réfléchir.

Je ne reviendrai plus sur ce fil, salut.

[erff]

Bonjour,

De ce que je vois, les propositions ne fonctionnent pas (même si je n'ai évidemment pas tout regardé).

• Par exemple 1,3,9,16,27,58 (pour 95) ne permet pas d'atteindre 24=16+8=16+3+3+1+1 (il faut 5 pièces). Cela se remarque car 8 "consomme" déjà 4 pièces.
• 1 3 9 16 27 58 ne permet pas d'avoir en 4 pièces 16+8=24 car 8=3+3+1+1
• De même que 1, 4, 9, 16, 38, 49 pour 108. 7 nécessite déjà 4 pièces (4,1,1,1) donc cette combinaison n'atteint pas 23=16+7=16+4+1+1+1 avec 4 pièces.
• ...

Une proposition:
Avec un raisonnement "récursif" en cherchant à consommer peu de pièces pour les petits nombres, j'arrive à une proposition qui je pense ne doit pas être trop éloignée de l'optimum (à vérifier n'est-ce pas).
1,2,5,8,11,25, qui modestement ne permet pas de réaliser mieux que tous les entiers jusqu'à 63 avec 4 pièces (car 64 = 25+25+11+2+1).

Bon dimanche

[vgondr98]

De même que 1, 4, 9, 16, 38, 49 pour 108. 7 nécessite déjà 4 pièces (4,1,1,1) donc cette combinaison n'atteint pas 23=16+7=16+4+1+1+1 avec 4 pièces.

9 + 9 + 4 + 1 = 23 donc 4 pièces permet bel et bien d'obtenir 23.

[polo974]

24 = 9 + 9 + 3 + 3

23 = 9 + 9 + 4 + 1

Grillé par vgondr98... pour un

[erff]

Re,

Effectivement, erreur de ma part, car j'ai supposé à tort qu'il fallait utiliser le plus gros billet à chaque fois, ce qui simplifie grandement le problème (et les possibilités) car il n'y a pas de redondance dans l'écriture des sommes .
Bien à vous

[polo974]

Heureusement qu'en euros, on ait garder une logique 1,2,5...
Je vous dit pas les prise de tête pour payer et rendre la monnaie sinon...

[Marcelus]

Bonjour Dalidou, et à tous,

De ton côté Marcelus, tu as caché dès le départ des informations (ton programme et le fait que tu as trouvé des 108 comme chiffre maximal), tout en disséminant des fausses (ta super formule), ce qui n'était pas très cool vu le temps que j'ai perdu à faire mes tests. Ce n'est pas vraiment une démarche collaborative et «*scientifique*». Si tu as bien ri de te moquer de moi, tant mieux pour toi. Je ne sais pas si c'est le bon forum pour ça, je te laisse y réfléchir.

Je ne reviendrai plus sur ce fil, salut.

Il y a un énorme quiproquo

En premier lieu, si j'ai froissé quelqu'un, ça n'est absolument pas de manière intentionnelle, et je m'en excuse.


Je pense, cher Dalidou, qu'il y a une mauvaise compréhension concernant mes intentions.
Que tu ait mal compris, ou bien que se soit moi qui me soit mal exprimé, je tiens à essayer de dissiper ce malentendu car je t'apprécie beaucoup et j'ai bien aimé les échanges que nous avons eu.


Pour commencer, j'ai compris que cette très intéressante énigme était une sorte de défi que tu lançais, je ne l'ai donc pas considéré comme un travail collaboratif pour lequel il aurait effectivement fallu partager immédiatement la moindre information, ce qui explique que je n'ai pas parlé de suite de mon programme, et tu ne me l'as pas non plus demandé.

Concernant la fausse formule que j'ai donné, elle avait 2 buts, en plus d'essayer d'ajouter un petit trait d'humour peut-être mal dosé.
Le premier but était d'essayer d'avoir une réaction de la part d'autres membres, en proposant une formule qui, comme tu l'as remarqué, ne contenait pas la variable du nombre de billets utilisables. En mettant une "erreur" tellement énorme, j'espérais ainsi attirer plus de monde dans ce sujet, car à part nous 2, il n'y avait malheureusement pas grand monde intéressé.
Le deuxième but de cette formule consistait à fournir un indice en indiquant une valeur qui serait potentiellement atteignable, sans avoir à donner la solution, car cela aurait immédiatement plié le game.

Je précise que, sauf erreur de ma part, cette "fausse" formule n'a absolument aucune utilité pour quelque stratégie que se soit.
Pour autant que je sache, aucune méthode de résolution de l'énigme, qu'elle soit mathématique, graphique, ou informatique ne peut se baser sur cette "formule", elle ne peut donc pas envoyer quelqu'un sur une fausse voie, d'autant plus que l'unique "promesse" que fait cette fausse formule est de prédire la valeur maximale que l'on devrait pouvoir obtenir ... et cette valeur est vraie.


Sur le sentiment que tu as concernant le fait que je me serais bien moqué de toi et que j'aurais bien rigolé à tes dépends, ce n'est absolument pas le cas, et si tu l'as vu comme cela j'en suis vraiment navré et je m'en excuse ... publiquement.

Il me semble avoir écris que je me suis bien amusé et que j'ai bien rigolé, et c'est vrai.
J'ai trouvé cette énigme très divertissante et je me suis bien amusé à essayer de trouver comment je pourrai la résoudre, surtout avec les "outils" très rudimentaires que j'ai à ma disposition en ce moment.
Concernant le coté "rigolade", le terme est peut-être un peu exagéré car ce n'est pas dans ce forum que j'ai le plus rigolé ces derniers temps, mais ce terme ne désignait nullement ta personne, je faisais simplement référence aux échanges que nous avons eu et sur le ton un peu humoristique qu'il m'a semblé détecter.

Je n'ai aucune raison de me moquer de toi ou de rire à tes dépends, j'ai bien aimé l'énigme que tu as créé, même si je ne te connais pas beaucoup, je t'apprécie grandement, et je suis vraiment navré que tu ais mal interprété mes propos et mes intentions, mais peut-être est-ce de ma faute d'avoir pensé que nous étions en phase sur le second degré, ou peut-être me suis-je mal exprimé.

J'espère qu'à la suite de ce message, ainsi que du message privé que je t'ai préalablement adressé, ce malentendu sera dissipé



Je tiens à ajouter une dernière chose un peu plus en rapport avec l'enigme elle-même :

je ne suis ni un spécialiste en mathématiques, ni un spécialiste en informatique, par conséquent, les solutions que j'ai donné demandent quand même a être vérifiées, et même si je pense que c'est le cas, je ne peux pas non plus affirmer que 108 soit le maximum, je n'ai ni la légitimité, ni les compétences pour affirmer cela.

[erff]

Bonsoir,

Du coup je n'arrive pas à mieux que 108 donc on peut supposer raisonnablement qu'on ne peut pas faire mieux.
Pour le délire j'ai regardé ce qui se passait si on ne disposait non pas de 6 mais de 7 pièces différentes. Dans ce cas j'arrive à former au mieux tous les nombres entre 1 et 162 avec les pièces suivantes : [1,4,10,15,37,50,71] ou [1,5,8,25,31,52,71].