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é ?

33Curieuros

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 !

66 réflexions sur “Les billets du Curiolande

  • 27 janvier 2016 à 19 h 49 min
    Permalien

    [eurêka !]
    15*33+2*64+126+251=1000, avec 19 billets. Le compte est bon!

    Répondre
    • 27 janvier 2016 à 20 h 55 min
      Permalien

      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.

      Répondre
      • 27 janvier 2016 à 22 h 41 min
        Permalien

        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^^

        Répondre
        • 28 janvier 2016 à 11 h 01 min
          Permalien

          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 !

          Répondre
          • 30 janvier 2016 à 14 h 34 min
            Permalien

            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.

    • 27 janvier 2016 à 22 h 53 min
      Permalien

      [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

      Répondre
  • 27 janvier 2016 à 23 h 00 min
    Permalien

    [eurêka !]
    autre solution: 13×33 + 5×64 + 251, toujours 19 billets.

    Répondre
  • 27 janvier 2016 à 23 h 04 min
    Permalien

    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.

    Répondre
  • 27 janvier 2016 à 23 h 19 min
    Permalien

    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…

    Répondre
  • 27 janvier 2016 à 23 h 22 min
    Permalien

    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?

    Répondre
    • 28 janvier 2016 à 11 h 05 min
      Permalien

      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 ») ^^ !

      Répondre
  • 27 janvier 2016 à 23 h 22 min
    Permalien

    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

    Répondre
  • 27 janvier 2016 à 23 h 35 min
    Permalien

    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…

    Répondre
  • 27 janvier 2016 à 23 h 39 min
    Permalien

    [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

    Répondre
    • 27 janvier 2016 à 23 h 55 min
      Permalien

      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<

      Répondre
  • 28 janvier 2016 à 0 h 13 min
    Permalien

    [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€

    Répondre
      • 28 janvier 2016 à 11 h 09 min
        Permalien

        Jolie méthode ! Elle vaut largement la mienne ! ^^

        Répondre
  • 28 janvier 2016 à 0 h 15 min
    Permalien

    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..

    Répondre
  • 28 janvier 2016 à 0 h 52 min
    Permalien

    [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).

    Répondre
    • 28 janvier 2016 à 1 h 27 min
      Permalien

      Dans votre raisonnement, pourquoi écartez-vous le billet de 501 et partez direct sur le billet de 251 ?

      Répondre
      • 28 janvier 2016 à 2 h 54 min
        Permalien

        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).

        Répondre
  • 28 janvier 2016 à 1 h 33 min
    Permalien

    J’ai trouvé la même solution, très facilement. Comment? Matlab!!

    Répondre
  • 28 janvier 2016 à 2 h 21 min
    Permalien

    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 ?

    Répondre
    • 28 janvier 2016 à 11 h 12 min
      Permalien

      Sachant que 501×19 fait déjà 9519…

      Répondre
      • 28 janvier 2016 à 12 h 47 min
        Permalien

        Je n’ai jamais aimé les billets trop gros, je suis sur que Léon Dem non plus …

        Répondre
    • 30 janvier 2016 à 11 h 48 min
      Permalien

      Et non, rien à faire avec moins de 20 billets. Il en faut une bonne cinquantaine.

      Répondre
      • 30 janvier 2016 à 11 h 59 min
        Permalien

        Non, pardon, la meilleure solution est à 27 billets :
        1 x 33 + 7 x 64 + 19 x 501

        Répondre
        • 30 janvier 2016 à 23 h 39 min
          Permalien

          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.

          Répondre
          • 31 janvier 2016 à 16 h 01 min
            Permalien

            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]

  • 28 janvier 2016 à 2 h 34 min
    Permalien

    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 ! ;))

    Répondre
    • 28 janvier 2016 à 11 h 15 min
      Permalien

      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… ^^

      Répondre
      • 28 janvier 2016 à 16 h 22 min
        Permalien

        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 !

        Répondre
  • 28 janvier 2016 à 4 h 12 min
    Permalien

    [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.

    Répondre
  • 28 janvier 2016 à 8 h 29 min
    Permalien

    Il y a 344 sommes superieure ou egale a 100 que l’on ne peut pas payer a Curiolande. La plus grande est 847.

    Répondre
    • 28 janvier 2016 à 11 h 16 min
      Permalien

      Rhô ! Monsieur (madame ?) me grille l’énigme bonus proposée dans la solution ! ^^ (Force brute, ou logique mathématique ?)

      Répondre
      • 28 janvier 2016 à 13 h 16 min
        Permalien

        Bien vu hmm hmm.
        Et parmi les 557 sommes atteignables entre 100 et 1000, 22 ne le sont qu’avec 20 billets ou plus 😉

        Répondre
  • 28 janvier 2016 à 12 h 22 min
    Permalien

    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.

    Répondre
    • 28 janvier 2016 à 18 h 58 min
      Permalien

      Bravo! La solution la plus simple et la plus élégante jusqu’ici, à mon avis.

      Répondre
  • 28 janvier 2016 à 12 h 23 min
    Permalien

    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.

    Répondre
    • 28 janvier 2016 à 16 h 40 min
      Permalien

      Bonjour,

      Pourquoi dans votre raisonnement n’apparaît pas le billet de 501? Est-il éliminé d’office ?

      Répondre
      • 28 janvier 2016 à 17 h 13 min
        Permalien

        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

        Répondre
        • 28 janvier 2016 à 17 h 22 min
          Permalien

          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.

          Répondre
    • 29 janvier 2016 à 10 h 19 min
      Permalien

      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

      Répondre
      • 10 février 2016 à 12 h 19 min
        Permalien

        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…

        Répondre
  • 28 janvier 2016 à 14 h 54 min
    Permalien

    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

    Répondre
    • 28 janvier 2016 à 14 h 55 min
      Permalien

      Arg, le site a bouffé l’indentation, désolé.

      Répondre
  • 28 janvier 2016 à 15 h 58 min
    Permalien

    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

    Répondre
    • 28 janvier 2016 à 18 h 31 min
      Permalien

      pour le 100 :
      33 + 64 et une pièce de 3 bien sur 🙂

      Répondre
  • 28 janvier 2016 à 18 h 30 min
    Permalien

    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

    Répondre
  • 28 janvier 2016 à 18 h 35 min
    Permalien

    [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.

    Répondre
  • 29 janvier 2016 à 12 h 59 min
    Permalien

    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.

    Répondre
  • 29 janvier 2016 à 23 h 10 min
    Permalien

    [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).

    Répondre
    • 29 janvier 2016 à 23 h 28 min
      Permalien

      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).

      Répondre
  • 1 février 2016 à 21 h 45 min
    Permalien

    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

    Répondre
    • 10 février 2016 à 13 h 11 min
      Permalien

      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

      Répondre
      • 10 février 2016 à 13 h 14 min
        Permalien

        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

        Répondre
        • 10 février 2016 à 13 h 16 min
          Permalien

          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

          Répondre
  • 5 février 2016 à 20 h 16 min
    Permalien

    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

    Répondre
  • 15 février 2016 à 0 h 16 min
    Permalien

    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

    Répondre
  • 29 février 2016 à 22 h 42 min
    Permalien

    Et pour faire l’appoint pour 100 € ? Et si dans l’énoncé c’est strictement supérieur à 100€, on cherche pour 101 € ?

    Répondre
  • 8 mars 2016 à 1 h 58 min
    Permalien

    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.

    Répondre
  • 1 mars 2018 à 11 h 12 min
    Permalien

    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

    Répondre

Répondre à tatayoo Annuler la réponse.