Les billets du Curiolande
Le ministre des finances du Curiolande a récemment ordonné le remplacement de tous les billets de banque du pays (ce qu’il a fait des pièces fera l’objet d’un autre récit). Désormais, il n’y a plus en circulation que des billets de 33, 64, 126, 251 et 501 curieuros. Un décret impose aux citoyens comme aux visiteurs de payer toutes leurs dépenses supérieures à 100 curieuros exclusivement en billets, et de toujours faire l’appoint.
Léon Dem, de passage au Curiolande, souhaite acheter une estampe curiolandienne d’une valeur de 1 000 curieuros ; aussi remet-il au vendeur cette somme exacte, sous la forme de quelques billets (moins d’une vingtaine). Combien de billets de chaque sorte a-t-il utilisé ?
N’hésitez pas à proposer vos pistes de solution dans les commentaires, voire d’y poster votre solution, à la condition de précéder celle-ci d’une mention du type [eurêka !] ou [spoiler] !
Bon jeu !
[eurêka !]
15*33+2*64+126+251=1000, avec 19 billets. Le compte est bon!
Bravo, j’avais obtenu le même résultat. Vous avez employé une méthode particulière, ou vous aviez comme moi un algo « sac à dos » sous la main ?
Parce que je me dis que ce ne doit pas être un hasard si les dénominations des billets sont furieusement proches de puissances de 2 (32, 64, 128, 256, 512), donc j’essaie de voir si on ne peut pas aboutir au résultat en partant de la décomposition binaire de 1000 (1000 = 512 + 256 + 128 + 64 + 32 + 8), mais pour le moment je patauge.
pour ma part j’ai cherché de ce coté mais je n’ai rien trouvé
du coup j’ai remarqué que 2*33=64+2, j’ai donc approché 1000 avec des billets de 64 que j’ai remplacé par des 2×33 ensuite
251+5*64+13*33, 19 billets le compte est bon^^
Bravo ! (Il y a deux solutions possibles à 19 billets).
Il existe une méthode autre que la « force brute », qui permet de trouver la solution en quelques coups de cuillère à schtroumpf, je la détaillerais dans un prochain billet !
J’ai trouvé la solution 13*33+5*64+251, en essayant d’abord quel pouvait être le plus gros billet (ici 251, car 501 ne donnait rien), puis en utilisant les règles de congruence des combinaisons de 33 et 64 modulo 33, pour le reste. Un peu bidouille, un peu arthmétique.
[eurêka !]
j’obtiens également la solution précédente (15*33+2*64+1*126+251)
Mais, j’ai aussi : 13*33+5*64+251 (19 billets aussi)
mais j’avoue que j’utilise la « force brute » a savoir un bout de code qui calcule toute les solutions !
j’ai également vu la proximité, voire l’égalité avec les puissances de 2 mais pas pu en déduire une méthode de résolution
[eurêka !]
autre solution: 13×33 + 5×64 + 251, toujours 19 billets.
En force brute, on trouve qu’il n’y a que deux solutions, celle précédemment citée (256 + 126 + 2×64 + 15*33) à 19 billets, et celle-ci (256 + 5*64 + 13*33) à 19 billets aussi. Je ne sais pas s’il y a une manière subtile de retrouover ces résultats par contre.
Il doit y avoir… J’ai noté qu’en notant tous les multiples des petits coupures, on arrivait toujours à une valeur supérieure à 250 et que donc il fallait trouver un 74x qui correspondrait aux 25y qu’on pouvait avoir, avec x et y non nuls et x+y = 10…
Je n’ai trouvé que la solution à 13*33.
mais c’est aussi de la force brute…
Pour les billets ok, mais j’ai pas trouvé ce que les câpres viennent faire dans cette galère. Est-ce parce que le câpre hisse?
Le câprier est l’emblème national du Curiolande, et aussi un satané arbuste que je n’arrive pas à faire pousser. C’est une référence qui revient souvent dans les billets que je signe sur mes différents blogs ; un « oeuf de Pâques » pour lecteurs fidèles qui ont de bons yeux (à l’image du lapin du métro de la série d’énigmes « Jeux de l’oie métropolitains ») ^^ !
Une grosse feuille de calcul Open Office le fait aussi avec plusieurs niveaux de sous-tableaux… On a sous les yeux toutes les possibilités… Il y a 2 fois « 1000 ». Mdr.
0 64 128 192 256 320 384 448 512 576 640 251 315 379 443 507 571 635 699 763 827 891
33 97 161 225 289 353 417 481 545 609 673 284 348 412 476 540 604 668 732 796 860 924
66 130 194 258 322 386 450 514 578 642 706 317 381 445 509 573 637 701 765 829 893 957
99 163 227 291 355 419 483 547 611 675 739 350 414 478 542 606 670 734 798 862 926 990
132 196 260 324 388 452 516 580 644 708 772 383 447 511 575 639 703 767 831 895 959 1023
165 229 293 357 421 485 549 613 677 741 805 416 480 544 608 672 736 800 864 928 992 1056
198 262 326 390 454 518 582 646 710 774 838 449 513 577 641 705 769 833 897 961 1025 1089
231 295 359 423 487 551 615 679 743 807 871 482 546 610 674 738 802 866 930 994 1058 1122
264 328 392 456 520 584 648 712 776 840 904 515 579 643 707 771 835 899 963 1027 1091 1155
297 361 425 489 553 617 681 745 809 873 937 548 612 676 740 804 868 932 996 1060 1124 1188
330 394 458 522 586 650 714 778 842 906 970 581 645 709 773 837 901 965 1029 1093 1157 1221
363 427 491 555 619 683 747 811 875 939 1003 614 678 742 806 870 934 998 1062 1126 1190 1254
396 460 524 588 652 716 780 844 908 972 1036 647 711 775 839 903 967 1031 1095 1159 1223 1287
429 493 557 621 685 749 813 877 941 1005 1069 680 744 808 872 936 1000 1064 1128 1192 1256 1320
462 526 590 654 718 782 846 910 974 1038 1102 713 777 841 905 969 1033 1097 1161 1225 1289 1353
495 559 623 687 751 815 879 943 1007 1071 1135 746 810 874 938 1002 1066 1130 1194 1258 1322 1386
126 190 254 318 382 446 510 574 638 702 766 377 441 505 569 633 697 761 825 889 953 1017
159 223 287 351 415 479 543 607 671 735 799 410 474 538 602 666 730 794 858 922 986 1050
192 256 320 384 448 512 576 640 704 768 832 443 507 571 635 699 763 827 891 955 1019 1083
225 289 353 417 481 545 609 673 737 801 865 476 540 604 668 732 796 860 924 988 1052 1116
258 322 386 450 514 578 642 706 770 834 898 509 573 637 701 765 829 893 957 1021 1085 1149
291 355 419 483 547 611 675 739 803 867 931 542 606 670 734 798 862 926 990 1054 1118 1182
324 388 452 516 580 644 708 772 836 900 964 575 639 703 767 831 895 959 1023 1087 1151 1215
357 421 485 549 613 677 741 805 869 933 997 608 672 736 800 864 928 992 1056 1120 1184 1248
390 454 518 582 646 710 774 838 902 966 1030 641 705 769 833 897 961 1025 1089 1153 1217 1281
423 487 551 615 679 743 807 871 935 999 1063 674 738 802 866 930 994 1058 1122 1186 1250 1314
456 520 584 648 712 776 840 904 968 1032 1096 707 771 835 899 963 1027 1091 1155 1219 1283 1347
489 553 617 681 745 809 873 937 1001 1065 1129 740 804 868 932 996 1060 1124 1188 1252 1316 1380
522 586 650 714 778 842 906 970 1034 1098 1162 773 837 901 965 1029 1093 1157 1221 1285 1349 1413
555 619 683 747 811 875 939 1003 1067 1131 1195 806 870 934 998 1062 1126 1190 1254 1318 1382 1446
588 652 716 780 844 908 972 1036 1100 1164 1228 839 903 967 1031 1095 1159 1223 1287 1351 1415 1479
621 685 749 813 877 941 1005 1069 1133 1197 1261 872 936 1000 1064 1128 1192 1256 1320 1384 1448 1512
Méthode D:
Il faut sans doute au moins un billet de 251 — ou alors ce billet existe seulement pour nous tromper.
Avec un billet de 251, un seul de 126 est possible. Il faut un nombre impair de 33, ca ne laissait pas beaucoup de choix…
[eurêka ?]
Ayant remarqué que la différence entre les 2 plus gros billets était de 250 tout rond, j’ai opté pour payer avec 4 billets de 501, et le vendeur rend 4 billets de 251, pourquoi s’embêter à faire l’appoint? haha
Parce que c’est écrit dans le texte qu’il fait l’appoint?
Plus jeune, lors de vos examens, vous répondiez déjà à vos propres questions?
>o<
[eurêka !]
1000€ = 30 x 33€ + 10€ à rajouter
Si je remplace 2 billets de 33€ par 1 de 64€, je devrai rajouter en plus 2€
Si je remplace 4 billets de 33€ par 1 de 126€, je devrai rajouter en plus 6€
Si je remplace 8 billets de 33€ par 1 de 251€, je devrai rajouter en plus 13€
Si je remplace 16 billets de 33€ par 1 de 501€, je devrai rajouter en plus 27€
Je me débrouille donc pour avoir à rajouter 33€ au final (soit pile un petit billet) : 33 = 10 (du début) + 13 + 6 + 2 + 2 (en faisant les remplacements ad hoc)
Du coup 1000€ = (30-2-2-4-8+1) x 33€ + 2 x 64€ + 1 x 126€ + 1 x 251€
Joli !
Jolie méthode ! Elle vaut largement la mienne ! ^^
Sympa.
La solution est donnée plus haut.
Pour ma part, sans code, j’ai mis les multiples des billets et tâtonné. Puis, j’ai remarqué que certains multiples permettaient de diminuer le total: 4 billets de 64 faisaient: 256 soit 4 de plus que deux billets de 126. A partir de là, on arrive à trouver le compte… Voili voilou..
[eurêka !]
Trouvé les deux solutions proposées aussi.
Suis parti de 31*33=1023 en remarquant que pour « baisser » cette somme, il fallait grouper les billets par deux et échanger contre un billet de valeur supérieure. L’écart est de 2 pour les 33 au 64, 64 au 126 mais de 1 ensuite. Comme la quantité que j’avais est impaire, il me faut utiliser au moins un billet de 251, donc échanger 2*2*2=8 billets de 33 contre un de 251. J’arrive à 1010, puis 1006 en échangeant encore 4 billets de 33 contre deux de 64 (indispensable si je veux continuer les échanges).
Dans votre raisonnement, pourquoi écartez-vous le billet de 501 et partez direct sur le billet de 251 ?
Si je prends un billet de 501, me reste 499 à trouver. Même raisonnement, je pars de 16*33=528 donc 29 à perdre par mes échanges. Même si j’échange tous mes billets à perte (8*64, puis 4*126, 2*251 et enfin 1*501), je ne pourrais perdre 29 (27 maximum).
J’ai trouvé la même solution, très facilement. Comment? Matlab!!
Solution « brute force » en C# :
https://gist.github.com/thomaslevesque/39090dbd0d4529f4e4b4
251 x 1 + 126 x 1 + 64 x 2 + 33 x 15
Le problème de commencer à collectionner des estampes c’est qu’on y prend goût. Du coup, Léon Dem est retourné dans le Curioland pour y acheter sa deuxième estampe, beaucoup plus chère celle-la, à 10000 cuireuros. Comment a-t-il pu payer avec moins de 20 billets ?
Sachant que 501×19 fait déjà 9519…
Je n’ai jamais aimé les billets trop gros, je suis sur que Léon Dem non plus …
Et non, rien à faire avec moins de 20 billets. Il en faut une bonne cinquantaine.
Non, pardon, la meilleure solution est à 27 billets :
1 x 33 + 7 x 64 + 19 x 501
Bien-sur, cela a interloqué Léon. Il se sentait un peu perdu, et voulait mieux comprendre ce qu’il pouvait faire ou pas. Par exemple, quelle était la somme maximale multiple de 100 curioeuros qu’il pouvait payer avec 20 billets ? Et la somme maximale multiple de 1000 curioeuros ? Et ce n’est pas tout. On a beau pouvoir payer, il faut encore avoir les bons billets. Du coup, il vaut mieux choisir la somme multiple de 100 curioeuros qui offre le plus de combinaisons possibles de 20 billets ou moins, il se trouve qu’il en a une où l’on peu payer de 38 façons différentes.
Nombre de réponses possibles pour payer avec 20 billets ou moins des sommes multiples de 100 curieuros.
[URL=http://www.turboimagehost.com/p/25256671/jeter.jpg.html][IMG]http://s6d8.turboimg.net/t1/25256671_jeter.jpg[/IMG][/URL]
Le graphique est à l’adresse
http://www.turboimagehost.com/p/25256671/jeter.jpg.html
L’enveloppe a l’air calculable …
Bon, [eurêka !] une solution également, en tâtonnant bêtement à partir de 1000 et en retranchant 33, puis encore 33 et ainsi de suite. Le reste de chaque opération étant à compléter avec des combinaisons de valeurs assez élevées, la solution apparaît « relativement » facilement, d’autant que les multiples de 64 et 126 sont toujours pairs et donc si le reste est impair, il faut nécessairement utiliser un billet de 251…
Par contre, ce qui m’intrigue à fond, c’est quand je lis : « Un décret impose aux citoyens comme aux visiteurs de payer toutes leurs dépenses supérieures à 100 curieuros exclusivement en billets, et de toujours faire l’appoint. » ! Car dans ces conditions, pour payer des trucs à 101 ou 102 curieuros, je pense que ça va être chaud ! ;))
On est tout à fait d’accord. Et même au-delà de 501, il y a des valeurs impossibles (ça a failli faire une énigme, d’ailleurs, mais j’ai réfréné mes instincts pervers). C’est un décret stupide, mais je n’ai jamais dit que les décrets n’étaient pas parfois complètement crétins. Et pas seulement au Curiolande… ^^
Il suffit de passer un décret complémentaire imposant aux vendeurs de ne pratiquer que des prix pouvant être atteints exactement avec les billets existants !
[Eureka!]
J’ai trouvé la solution précédemment évoquée à la main.
Pour ce faire, je suis passé par le modulo 25. En effet, la somme des billets à utiliser devant égaler 100, la somme des modulos 25 desdits billets doit arriver à un multiple de 25.
33 est congru à 8 modulo 25, 64 est congru à 14 modulo 25, et les autres valeurs possibles sont congrues à 1 modulo 25.
Pour une somme arrivant à 25, on obtient trois possibilités après avoir exclu certaines propositions trivialement irréalisables (25*1, pour n’en citer qu’une) (en assimilant les billets congrus à 1 à un choix possible) : 3*8+1, 8+14+3*1 etc.
On procède de même pour 50, 75, et 100, sans résultat fonctionnel. Enfin, arrivé à 125, on tombe finalement sur 2*14+15*8+2, ce qui renvoie à 625 + 2 valeurs parmi 125, 250 et 500, et donc à 2*64+15*33+125+250.
D’où le résultat.
On remarquera par ailleurs qu’en utilisant la précédente méthode en étant plus attentif que je ne l’ai été, arrivé à 100, on sait que 8*3+1 font 25 soit 100+une valeur modulo 1 et que 9*8+2*14 font 100, soit 425 et donc en combinant deux fois la première combinaison avec la seconde, on obtient le même résultat.
Il y a 344 sommes superieure ou egale a 100 que l’on ne peut pas payer a Curiolande. La plus grande est 847.
Rhô ! Monsieur (madame ?) me grille l’énigme bonus proposée dans la solution ! ^^ (Force brute, ou logique mathématique ?)
Bien vu hmm hmm.
Et parmi les 557 sommes atteignables entre 100 et 1000, 22 ne le sont qu’avec 20 billets ou plus 😉
On cherche a, b, c, d nombres entiers positifs tels que:
a+b+c+d<ou= 20
33a + 64b + 126c + 251d = 1000
Il faut remarquer que 33=32+1, 64=2×32, 126=4×32-2, 251=8×32-5
donc : (a -2c -5d) + 32 (a + 2b + 4c + 8d) = 1000
Comme a est plus petit que 20, (a – 2c – 5d) aussi, donc 32 (a + 2b + 4c + 8d) réalise 992 (= 31 x 32) qui est le multiple de 32 juste en dessous de 1000.
donc :
(A) : a -2c -5d = 8 et (B) : a + 2b + 4c + 8d = 31
en faisant (B) – (A) devient (C) : 2b + 6c + 13 d = 23
Donc d = 0 ou d = 1
d = 0 est impossible, (C) devient : 23 = 2b + 6c qui est pair.
donc d=1
(C) devient (D) : 2b + 6c = 10
Donc
– soit c = 0, donc b = 5 et ainsi a = 13, on vérifie que
13×33 + 5×64 +0x64 + 1×251 = 1000
– soit c = 1, donc b = 2 et ainsi a = 15, on vérifie que
15×33 + 2×64 +1×64 + 1×251 = 1000
et dans les deux cas a + b+ c + d = 19
La réponse est donc 19 billets utilisés.
Bravo! La solution la plus simple et la plus élégante jusqu’ici, à mon avis.
eurêka !
On cherche a, b, c, d nombres entiers positifs tels que:
a+b+c+d<ou= 20
33a + 64b + 126c + 251d = 1000
Il faut remarquer que 33=32+1, 64=2×32, 126=4×32-2, 251=8×32-5
donc : (a -2c -5d) + 32 (a + 2b + 4c + 8d) = 1000
Comme a est plus petit que 20, (a – 2c – 5d) aussi, donc 32 (a + 2b + 4c + 8d) réalise 992 (= 31 x 32) qui est le multiple de 32 juste en dessous de 1000.
donc :
(A) : a -2c -5d = 8 et (B) : a + 2b + 4c + 8d = 31
en faisant (B) – (A) devient (C) : 2b + 6c + 13 d = 23
Donc d = 0 ou d = 1
d = 0 est impossible, (C) devient : 23 = 2b + 6c qui est pair.
donc d=1
(C) devient (D) : 2b + 6c = 10
Donc
– soit c = 0, donc b = 5 et ainsi a = 13, on vérifie que
13×33 + 5×64 +0x64 + 1×251 = 1000
– soit c = 1, donc b = 2 et ainsi a = 15, on vérifie que
15×33 + 2×64 +1×64 + 1×251 = 1000
et dans les deux cas a + b+ c + d = 19
La réponse est donc 19 billets utilisés.
Bonjour,
Pourquoi dans votre raisonnement n’apparaît pas le billet de 501? Est-il éliminé d’office ?
(en dehors de ça chapeau !)
eurêka ! suite et complément
… je n’avais pas vu le billet de 501, alors voici le complément :
Même raisonnement en rajoutant « e » billets de 501 (e = 1 ou 0) et en remarquant que 501 = 32×16 -11
l’équation (A) devient : a -2c -5d -11e = 8
et (B) : a + 2b + 4c + 8d + 16 e = 31
et (C) : 2b + 6c + 13 d +27e = 23 donc e = 0,
donc on est ramené au cas précédent.
et en complément:
… puisque a + 2b + 4c + 8d = 31 et d = 1 on a :
(D) : a + 2b + 4c = 23 (= 31 – 8×1)
de 2b + 6c = 10 on a (E) : b + 3c = 5 et donc par soustraction:
(D) – (E) : a + b + c = 18 (= 23 – 5)
et comme d = 1, e = 0 , qu’on a bien exhibé les deux solutions:
a + b + c + d + e = 19 billets
eurêka !
… et je viens de me relire, j’ai mis 64 à la place de 126 à la fin alors je corrige en demandant de me pardonner cette faute de frappe (!):
On cherche a, b, c, d nombres entiers positifs tels que:
a+b+c+d<ou= 20
33a + 64b + 126c + 251d = 1000
Il faut remarquer que 33=32+1, 64=2×32, 126=4×32-2, 251=8×32-5
donc : (a -2c -5d) + 32 (a + 2b + 4c + 8d) = 1000
Comme a est plus petit que 20, (a – 2c – 5d) aussi, donc 32 (a + 2b + 4c + 8d) réalise 992 (= 31 x 32) qui est le multiple de 32 juste en dessous de 1000.
donc :
(A) : a -2c -5d = 8 et (B) : a + 2b + 4c + 8d = 31
en faisant (B) – (A) devient (C) : 2b + 6c + 13 d = 23
Donc d = 0 ou d = 1
d = 0 est impossible, (C) devient : 23 = 2b + 6c qui est pair.
donc d=1
(C) devient (D) : 2b + 6c = 10
Donc
– soit c = 0, donc b = 5 et ainsi a = 13, on vérifie que
13×33 + 5×64 +0x126 + 1×251 = 1000
– soit c = 1, donc b = 2 et ainsi a = 15, on vérifie que
15×33 + 2×64 +1×126 + 1×251 = 1000
et dans les deux cas a + b+ c + d = 19
La réponse est donc 19 billets utilisés.
Bonjour,
la solution est élégante, mais qu’est-ce qui vous permet d’affirmer que a-2c-5d est positif? On pourrait théoriquement avoir:
a-2c-5d=-24
a+2b+4c+8d=32
Remarque intéressante, puisque pas développée :
0<=2c+5d<=20 et 0<=a<=20 donc -20<=a-2c-5d<=20
Le seul multiple de 32 entre 980 et 1020 est 992, et on peut continuer…
eurêka !
En brute force mais dans un temps humainement acceptable, et en python s’il y en a qui sont intéressés :
from copy import copy
billets = {33 : 0, 64 : 0, 126 : 0, 251 : 0, 501 : 0}
def curioland(candidat, total):
for num in candidat:
if num > total:
continue
solution = copy(candidat)
solution[num] += 1
if num == total:
print repr(solution)
else:
curioland(solution, total – num)
curioland(billets, 1000)
Puis on exécute :
time python curioland.py | sort -u
{64: 2, 33: 15, 251: 1, 501: 0, 126: 1}
{64: 5, 33: 13, 251: 1, 501: 0, 126: 0}
real 2m46.365s
user 2m45.841s
sys 0m0.580s
Arg, le site a bouffé l’indentation, désolé.
Même raisonnement que beauvais
J’ai tout d’abord remarqué que c’est presque des puissances de 2:
33*2 = 64 + 2
64*2 = 126 + 2
126*2 = 251 + 1
251*2 = 501 + 1
Aussi les deltas sont tous positifs et les changement de puissance produisent soit des delta de 1 soit de 2.
Pour attendre 1000, je suis parti d’une liasse de billets de 33. Avec 31 billets j’atteint 1023. A chaque fois que je fais une fusion de 2 billets (f2) de 33 je diminue le montant de 2; si je fais une fusion de 4 billets (f4) (pour en obtenir un seul), je diminue de 6 (4*33 = 2*(64 + 2) = 126 + 2*2 + 2), en continuant pour 8 billets (f8) on obtient 13 (8*33 = 2*(126 + 6) = 251 + 2*6 + 1).
A partir de la il faut rechercher le nombre de fusions nécessaires (n2, n4, n8 le nombre de fusion pour respectivement f2, f4 et f8)
n2*2+n4*6+n8*13 = 23.
Les n2, n4, n8 ne peuvent pas être négatif, et on a besoin d’obtenir un nombre impaire. donc n8 est forcement égale à 1. Le nombre de billet sera donc de réduit à
n2*2 + n4*6 = 10
ici, intuitivement on voit deux solutions:
n2 = 5, n4 = 0 et n2 = 2 et n4 = 1
avec la première solution
31 – (8-1) – 5*(2-1) = 19 cartes
dont 5 billets à 64 et 1 billet à 251 (le reste est à 33)
13*33 + 5*64 + 251
seconde solution
31 – (8-1) – (4-1) – 2*(2-1) = 19 cartes
dont 2 billets de 64, 1 billet de 126, 1 billet de 251
15*33 + 2*64 + 126 + 251
Plus compliqué: comment faire pour payer 100 avec l’appoint?
33*3 = 99
33 + 64 = 97
126 > 100
pour le 100 :
33 + 64 et une pièce de 3 bien sur 🙂
je suis tombé sur la solution 13×33 + 5×64+251 sans force brute et avec un raisonnement très simple je dirais:
– on cherche à obtenir un montant rond
– on n’a que des billets de valeurs bizarres
==> combiner les billets pour avoir des valeurs qui tombent rond. Puis combiner les multiples de ces valeurs.
j’avais 4 candidats :
(1) – 64 +126 = 190
(2) – 2×33+64 = 130
(3) – 3×33+251 = 350
(4) -3×33+501 =600
j’ai réalisé les multiples de ces combinaisons restant inférieures à 1000, et observé que 5x (2)+(3) = 1000
[euréka]
33, 64, 126, 251 et 501 : presque des puissances de 2.
1000 : presque une puissance de 2.
Mais 1000 est trop éloigné de 1024 pour tenir comme somme de « presque puissance de 2 » (alors que cela marche par exemple avec 1003=501+251+251)
Essayons : 33 * 31 = 1023, puis descendons avec des regroupements :
33*29+64 = 1021 ; 33*27+64*2 = 1019 ; 33*25+64*3 = 1017 ;
=> on baisse de 2 à chaque fois, on ne va pas tomber sur 1000.
Regroupons quand même encore un peu :
33*21+64*5 = 1013 ;
Regroupons maintenant quatre 64 en un 251 :
33*21+64+251 = 1008
maintenant, on peut regrouper huit 33 pour arriver à 1000 avec moins de 20 billets :
33*13+64*5+251 = 1000
Treize billets de 33, cinq de 64 et un de 251 font une somme de 1000, avec dix-neuf billets.
Eureka
J’ai aussi trouvé les 2 réponses mais avec une méthode un peu moins brutale.
J’ai d’abord cherché les combinaisons de billets qui pouvaient donner une dizaine ronde (pex 350, 130, 660, etc.). On prend 1 x 33 et on regarde comment compléter pour ariver à une dizaine ronde. Puis on prend 2 x 33 et on répete l’opération. Une fois qu’on a fait le tour des billets de 33, on fait pareil pour ceux de 64, etc. En tout, il n’y a que 22 possibilités d’avoir une dizaine ronde. Et pour finir, on regarde lesquels de ces 22 nombres peuvent faire une somme de 1000. Et on obtient la quantité de billets nécessaires.
[eurêka !]
Bonjour,
je note, plus haut, des solutions bien plus élégantes que celle ci-dessous :
Je remarque que :
64 = 33*2 – 2
126 = 33*4 – 6
251 = 33*8 – 13
501 = 33*16 – 27
La solution se trouve dans les multiples de 33 et les différences (-2 ; -6 ; -13 ; -27) permettront de tomber juste.
On voit que :
33*30 = 990 ==> pas assez
33*31 = 1023 ==> trop mais je vais pouvoir utiliser les différences (-2 ; -6 ; -13 ; -27) pour tomber juste.
Donc 23 de trop que je décompose en deux possibilités :
1ère possibilité :
2*2 + 1*6 + 1*13 qui correspondent à l’utilisation de 2 billets de 64 ; 1 billet de 126 et 1 billets de 251. Il ne reste plus qu’à compléter avec les multiples de 33 soit 15 billets de 33.
2ème possibilité :
5*2 + 1*13 qui correspondent à l’utilisation de 5 billets de 64 et 1 billets de 251. Il ne reste plus qu’à compléter avec les multiples de 33 soit 13 billets de 33.
Ce n’est pas joli-joli mais les deux seules possibilités trouvées par la méthode correspondent bien aux seules possibilités trouvées par nos chers usagers de la méthode « force brute ».
Cette « méthode » « semble » aussi montrer que certaines sommes à payer du type n*33+11 ; n*33+9 ; n*33+7 ; n*33+5; n*33+3 ; n*33+1 ne sont pas accessibles (sauf cas de grands-multiples).
ERRATUM
Cette « méthode » « semble » aussi montrer que certaines sommes à payer du type n*33+11 ; n*33+9 ; n*33+7 ; n*33+5; n*33+3 ; n*33+1 ne sont pas accessibles (sauf cas de grands-multiples).
LIRE PLUTOT
Cette « méthode » « semble » aussi montrer que certaines sommes à payer (>501) du type n*33-11 ; n*33-9 ; n*33-7 ; n*33-5; n*33-3 ; n*33-1 ne sont pas accessibles (sauf cas de grands-multiples).
eurêka !
Bonjour à tous,
Pour ceux qui comme moi ont cherché à « informatiser » le problème je vous donne le code VBA qui tourne sous Excel.
Merci à l’auteur du blog pour ces belles énigmes.
Dim MAX, Somme As Integer
Dim trouver As Boolean
MAX = 20
trouver = False
Somme = 0
‘Billet de 33 Curieuros
For a = 0 To MAX
‘Billets de 64 Curieuros
For b = 0 To MAX
‘Billets de 126 Curieuros
For c = 0 To MAX
‘Billets de 251 Curieuros
For d = 0 To MAX
‘Billets de 501 Curieuros
For e = 0 To MAX
‘Controler si le nombre de billets dépasse les 20 pour sortir de la boucle
If a + b + c + d + e > 20 Then Exit For
Somme = 33 * a + 64 * b + 126 * c + 251 * d + 501 * e
‘Controler si la somme est égale à 1000 Curieuros
If Somme = 1000 Then
trouver = True
‘Puisque le résultat est trouver sortir de la boucle et aller vers l’affichage des résultats
GoTo solution
ElseIf Somme > 1000 Then Exit For
End If
Next e
Next d
Next c
Next b
Next a
solution:
If trouver Then
MsgBox « a= » & a & « , b= » & b & « , c= » & c & « , d= » & d & « , e= » & e
Else
MsgBox « Pas de solution »
End If
Avec solutions multiples :
Sub curieuros()
Dim MAX, Somme As Integer
Dim solutions As String
MAX = 20
For a = 0 To MAX ‘Billet de 33 Curieuros
For b = 0 To MAX – a ‘Billets de 64 Curieuros
For c = 0 To MAX – a – b ‘Billets de 126 Curieuros
For d = 0 To MAX – a – b – c ‘Billets de 251 Curieuros
For e = 0 To MAX – a – b – c – d ‘Billets de 501 Curieuros
‘Controler si le nombre de billets dépasse les 20 pour sortir de la boucle
Somme = 33 * a + 64 * b + 126 * c + 251 * d + 501 * e
‘Controler si la somme est égale à 1000 Curieuros
If Somme = 1000 Then
solutions = solutions & IIf(Len(solutions) 1000 Then Exit For
End If
Next e: Next d: Next c: Next b: Next a
MsgBox solutions
End Sub
2ème tentative, des caractères ne sont pas passés …
Sub curieuros()
Dim MAX, Somme As Integer
Dim solutions As String
MAX = 20
For a = 0 To MAX ‘Billet de 33 Curieuros
For b = 0 To MAX – a ‘Billets de 64 Curieuros
For c = 0 To MAX – a – b ‘Billets de 126 Curieuros
For d = 0 To MAX – a – b – c ‘Billets de 251 Curieuros
For e = 0 To MAX – a – b – c – d ‘Billets de 501 Curieuros
Somme = 33 * a + 64 * b + 126 * c + 251 * d + 501 * e
‘Controler si la somme est égale à 1000 Curieuros
If Somme = 1000 Then
solutions = solutions & IIf(Len(solutions)1000 Then Exit For
End If
Next e: Next d: Next c: Next b: Next a
MsgBox solutions
End Sub
bon j’y arriverais pas : je simplifie un peu
Sub curieuros()
Dim MAX, Somme As Integer
Dim solutions As String
MAX = 20
For a = 0 To MAX ‘Billet de 33 Curieuros
For b = 0 To MAX – a ‘Billets de 64 Curieuros
For c = 0 To MAX – a – b ‘Billets de 126 Curieuros
For d = 0 To MAX – a – b – c ‘Billets de 251 Curieuros
For e = 0 To MAX – a – b – c – d ‘Billets de 501 Curieuros
Somme = 33 * a + 64 * b + 126 * c + 251 * d + 501 * e
‘Controler si la somme est égale à 1000 Curieuros
If Somme = 1000 Then
solutions = solutions & vbCrLf & « 33 * » & a & » + 64 * » & b & » + 126 * » & c & » + 251 * » & d & » + 501 * » & e
ElseIf Somme > 1000 Then Exit For
End If
Next e: Next d: Next c: Next b: Next a
MsgBox solutions
End Sub
eurêka !
J’ai deux idées de solution pour le cas général:
le but est de résoudre une équation du type (E): z=x1*33 +x2*64 +x3*126 +x4*251 d’inconnu x=(x1,x2,x3,x4) de N^4 (avec z un entier naturel).
Solution 1:
remarquons gcd(33,126)=3 , gcd(64,251)=1 et gcd(3,64,251)=1;
alors (E) peut s’écrire:
z=3*(11*x1+42*x3) +64*x2 +251*x4
pour tout entier y<=z on note:
S_y1 l'ensemble des solution naturel de l'eq 64a+251b=y (c'est une equation diophantienne classique).
S_y2 l'ensemble des solution naturel de l'eq 11a+42b=y
S_3 l'ensemble des solution naturel de l'eq 3a+b=z
pour chaque couple (a',b') de S_3, on regarde les solution de S_a'2 et S_b'1. l'ensemble des solution s'écrit alors
S={ (x1,x2,x3,x4) tq: pour tout (a',b') de S_3 on a (x1,x3) apartient à S_a'2 et (x2,x4) apartient à S_b'1 }
Solution 2 "géométrique" :
on choisit de résoudre dans R^4 et d'isoler ensuite les solutions entière.
On se place dans R^4 on considère la norme:
Norm(x)=abs(x1)*33 +abs(x2)*64 +abs(x3)*126 +abs(x4)*251
on note Bz le disque centré de rayon z pour cette norme, Bz est un polyhèdre convexe dont les sommet sont (z/33,0, 0, 0),(0,z/64, 0, 0),(0,0, z/126, 0), et(0,0, 0, z/251), (et leur opposé (-z/33,0, 0, 0),(0,-z/64, 0, 0),…)
il apparait alors que alors que l'ensemble des solutions de (E) est l'intersection de Bz et N^4.
On peut alors chercher les solutions faces par faces, chaque face de Bz est de dimension 3. on a alors une équation du même genre que (E)
mais avec 3 inconnu, on applique le même raisonnement sur chaque face..on obtiens enfin des équation diophantienne classique…
notons B_Z
eureka!
voici une solution proche d’une citée
il faut résoudre en entiers: 501x + 251y + 126z + 64t + 33u = 1000
ou X + Y + Z + T + U = 1000
ce qui s’écrit: X’ +Y’ + Z’ +T’ + U’ = 1 (mod 3)
comme X’=Y’=U’=0 on en déduit Z’+T’=1 (mod 3)
ce qui donne 3 couples possibles (Y’,T’) soit (0,1) (1,0) (2,2) et 21 couples possibles pour (y,t)
ensuite, on a aussi: X* + Y* +Z* + T* + U* = 10 (mod 11)
on calcule facilement les restes par 11 de X* Y* Z* T* U* pour chaque valeur de x,y,z;t,u (on voit comme signalé que x=0). Par ex; les valeurs possibles de Z* sont (0,5,10,4,9,3,8,2)
ensuite on teste les 21 couples (y,t) pour voir si le reste par 11 est correct
Par exemple pour (Y’T’)= (2,2), un des 5 couples (y,t) possible est (1,5),
ce qui donne T=128 T*=7 (mod 11) Z*=5 (mod 11) z=1 Z=126 U=1000-251-128-126=495=15×33
on élimine ainsi les (y,t) conduisant à des T trop grands ou des restes Z* impossibles
Et pour faire l’appoint pour 100 € ? Et si dans l’énoncé c’est strictement supérieur à 100€, on cherche pour 101 € ?
Modulo 31 ça paraît plus simple. 33, 64, 126, 251, 501 valent respectivement 2, 2, 2, 3, 5. 1000 vaut 8 modulo 31. Il faut trouver des sommes de 2, 3, et 5 qui totalisent 8 ou 39 ou 70 …
On ne peut pas avoir deux fois le 5. Ça ferait deux fois 501, ça dépasse.
Peut-on avoir une fois le 5 ? Pour atteindre 8 il faut ajouter le 3, mais 251 + 501 ne font pas 1000. Pour atteindre 39, il faut ajouter un nombre pair de 3 (sinon le total est pair), mais déjà à 2 on dépasse 1000. Il en faut donc 0. On a donc besoin de 17 fois 2. Mais même avec la plus petite coupure, 17 x 33 + 501, on dépasse 1000. Pour atteindre 70 ou plus, pareil on va dépasser largement.
Donc pas de 5, c’est à dire, pas de coupure 501.
Donc il faut atteindre 8, ou 39, ou 70 … Avec des sommes de 2 et 3 uniquement.
Pour atteindre 8, les rares possibilités 2 x 3 + 1 x 2 ou 4 x 2 ne donnent rien, je passe vite.
Pour atteindre 39, il faut un nombre impair de 3. 5 c’est trop. 3 x 3 ne donne rien, car il faut compléter par 15 fois 2, et avec la plus petite coupure, 15 x 33 + 3 x 251, on dépasse. Il n’y aurait donc que 1 x 3 qui pourrait marcher. Il faut donc compléter avec 18 x 2 pour atteindre 39.
Avant de conclure, on peut poursuivre et éliminer facilement les autres cas où la somme de 2 et de 3 fait 70 ou plus.
Concluons. Modulo 31, il n’y a que 18 x 2 + 3 qui pourrait marcher. Soit 18 parmi 33 ou 64 ou 126 + 251 = 1000. Trouvons donc une somme de 18 nombres parmi 33, 64, 126 qui totalisent 749. Si on retire 33, trouvons une somme de 18 nombres parmi 0, 31, 93, qui totalisent 155. Ça marche avec 15 x 0 + 2 x 31 + 1 x 93 ou avec 13 x 0 + 5 x 31. C’est tout.
Donc il faut prendre de chaque coupure soit 15, 2, 1, 1, 0 ou 13, 5, 0, 1, 0.
eureka!
Voici comment j’ai trouvé la solution
33 + 64 + 126 + 251 + 501 = 975 (A)
On constate que :
33 = 33
64 = 2 x 33 – 2 (B)
126 = 4 x 33 – 6
251 = 8 x 33 – 13
501 = 16 x 33 – 27 (C)
Comme il nous manque 25 à la ligne (A) pour avoir 1000, on cherche ce 25 dans les expressions ci-dessus ; à savoir dans la différence entre (B) et (C).
64 – 501 = 2 x 33 – 2 – 16 x 33 + 27
= -14 x 33 + 25
d’où 25 = 64 – 501 + 14 x 33
En addition ceci à la ligne (A) on aura :
975 + 25 = (33 + 64 + 126 + 251 + 501) + (64 – 501 + 14 x 33)
Après réduction on aura :
1000 = 15 x 33 + 2 x 64 + 126 + 251