![](/img/vague-bas-gauche.png) |
#1 - 04-01-2013 10:26:40
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
on ne peut pas tput acheter.
Bonjour à tous, Et très bonne année 2013 à tous les survivants du 21 décembre.
Je propose ici un problème classique de somme, très bien maitrisé avec 2 variables, nettement moins avec 3 et +. Vous disposez de pièces de 31, 73 et 97 unités. Quelle est la plus grande somme que vous ne pouvez pas faire ? Je l'ai fait à la main, j'ai juste vérifié l'exactitude avec une calculette. De la méthode, il en faut...
#2 - 04-01-2013 11:41:18
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
On ne peut pas tout acheteer.
Heu, je peux me tromper, mais il me semble qu'un problème similaire a été posé il y a moins de 6 mois (avec 4 valeurs si mes souvenirs sont bons !)
J'ai retrouvé :
http://www.prise2tete.fr/forum/viewtopic.php?id=10743
#3 - 04-01-2013 13:52:03
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
On ne peut pas toout acheter.
J pas compris et c quoi les variables ... Je les connais pas et j'ai pas appris j'ai que 12 ans et je suis en 3ème ...
#4 - 04-01-2013 15:45:39
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
On ne peut pas toout acheter.
J'ai trouvé 722 après une longue recherche sur excel, ce doit être bon... (J'ai listé toutes les sommes possibles avec ces 3 pièces).
#5 - 04-01-2013 15:49:52
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
on ne peut pas tout zcheter.
Les voilà : 31 62 73 93 97 104 124 128 135 146 155 159 166 170 177 186 190 194 197 201 208 217 219 221 225 228 232 239 243 248 250 252 256 259 263 267 270 274 279 281 283 287 290 291 292 294 298 301 305 310 312 314 316 318 321 322 323 325 329 332 336 340 341 343 345 347 349 352 353 354 356 360 363 364 365 367 371 372 374 376 378 380 383 384 385 387 388 389 391 394 395 396 398 402 403 405 407 409 411 413 414 415 416 418 419 420 422 425 426 427 429 433 434 436 437 438 440 442 444 445 446 447 449 450 451 453 456 457 458 460 461 462 464 465 467 468 469 471 473 475 476 477 478 480 481 482 484 485 486 487 488 489 491 492 493 495 496 498 499 500 502 504 506 507 508 509 510 511 512 513 515 516 517 518 519 520 522 523 524 526 527 529 530 531 533 534 535 537 538 539 540 541 542 543 544 546 547 548 549 550 551 553 554 555 557 558 559 560 561 562 564 565 566 568 569 570 571 572 573 574 575 577 578 579 580 581 582 583 584 585 586 588 589 590 591 592 593 595 596 597 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 619 620 621 622 623 624 626 627 628 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 650 651 652 653 654 655 656 657 658 659 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 (754 755 756 757 758 759 760)
#6 - 04-01-2013 16:44:24
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
on ne pzut pas tout acheter.
Golgot59 c'est OK pour toi, mais comment aurais tu fait sans le tableur ?
#7 - 05-01-2013 16:34:05
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
On ne peut pas tut acheter.
La plus grande somme que l'on ne peut pas obtenir est 722 .
#8 - 05-01-2013 18:22:56
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
On ne peut pas tout acheer.
Oui masab. Méthode employée ?
#9 - 06-01-2013 16:23:17
- pseudo
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 1
On ne peut as tout acheter.
Spoiler : [Afficher le message] 722, grace a un petit programme en python
def blabla2(n): l=range(31*n+73*n+97*n+1) for i in range(((31*n+73*n+97*n+1)/31)+1): for j in range(((31*n+73*n+97*n+1)/73)+1): for k in range(((31*n+73*n+97*n+1)/97)+1): try: l.remove(i*31+73*j+97*k) except: pass return l
#10 - 06-01-2013 17:10:40
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
On ne peut pas tout achteer.
Voici la justification de ma réponse ! Soient a,b entiers naturels premiers entre eux. Il est connu que tout entier n>=(a-1)*(b-1) peut s'écrire sous la forme n=u*a+v*b où u et v sont des entiers naturels. On applique ce résultat à a=31, b=73. On obtient que tout entier n>=30*72=2160 peut s'écrire sous la forme n=31*u+73*v où u et v sont des entiers naturels. A fortiori tout entier n>=2160 peut s'écrire sous la forme n=31*u+73*v+97*w où u, v et w sont des entiers naturels. Il reste à étudier les entiers n<2160. S'il existe u,v,w tels que n=31*u+73*v+97*w, alors on a u<=69, v<=29, w<=22. On est donc ramené à étudier un nombre fini de triplets (u,v,w) et à voir pour chacun d'eux si la relation n=31*u+73*v+97*w est vraie ou non. Un petit programme informatique montre alors que la plus grande somme que l'on ne peut pas obtenir est 722.
#11 - 06-01-2013 19:48:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
on ne peut pas toyt acheter.
D'accord, masab, je vois que sur la dernière partie tu fais appel à un programme. On peut sans, et sans se perdre dans une recherche au cas par cas....
#12 - 07-01-2013 10:30:53
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
n ne peut pas tout acheter.
La première séquence de 31 nombres consécutifs s'écrivant comme combinaison linéaire entière (CLE) de 31, 73 et 97 se trouve de 723 à 753 (inclus). A partir de là, il suffit d'ajouter les multiples successifs de 31 pour avoir tous les nombres. 722, lui ne peut pas s'écrire comme CLE de 31, 73 et 97, donc c'est la plus grand somme que l'on ne peut pas faire.
Je n'ai pas trouvé de formule vraiment générale à 3 nombres (pour 2 nombres premiers entre eux, je rappelle que la formule est pq-p-q).
Je n'ai pas trouvé de démonstration simple à l'aide de Bezout ou du résultat à 2 nombres sans devoir faire au moins un partie de recherche systématique (comme masab). Il n'est pas facile de prévoir les "trous" dans les CLE de 31 et 73 pour voir comment par congruence module 97 les boucher...
J'attends donc avec impatience la solution de nodgim et en particulier s'il existe une formule générale pour 3 nombres...
#13 - 07-01-2013 16:58:32
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
On ne eput pas tout acheter.
Il n'existe pas de formule générale pour 3 nombres et le problème est NP-difficile. En revanche, on démontre facilement que ce nombre existe toujours, ce qui est déjà pas mal.
#14 - 07-01-2013 17:28:29
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
On ne peut pas tout acheter..
Comme rivas, j'attends avec impatience la solution de nodgim, même s'il n'existe à priori pas de formule générale pour 3 nombres, car j'ai aussi cherché sans succès du côté de chez Bezout.
#15 - 07-01-2013 17:30:09
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
on ne peut pas tout axheter.
Merci titoufred pour les précisions. Voila peut-être un problème ouvert intéressant: trouver la formule générale encore inconnue dans ce cas...
Pour l'existence, si les nombres sont premiers deux à deux entre eux, vu qu'avec seulement 2 d'entre eux on peut générer tous les nombres à partir d'un certain rang, avec un troisième, cela est forcément le cas et forcément à partir d'un nombre plus petit ![smile](img/smilies/smile.png)
#16 - 07-01-2013 17:42:15
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Onn ne peut pas tout acheter.
J'ai écrit la moitié de ce que j'avais en tête, désolé...
En fait, ce nombre existe toujours pour n nombres premiers entre eux dans leur ensemble, sans nécessairement qu'ils soient premiers entre eux 2 à 2.
#17 - 07-01-2013 17:45:49
- rivas
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1106
- Lieu: Jacou
on ne pzut pas tout acheter.
OK désolé et merci pour ta clarification. J'étais un peu surpris ![smile](img/smilies/smile.png)
#18 - 07-01-2013 18:55:06
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
on ne peut pas tout acheyer.
Je suis flatté de constater que cette question éveille quelque intérêt. Je n'ai pas trouvé de solution générale, mais la méthode proposée ci dessous permet, puisque la question se pose, de conclure..qu'il ne peut y avoir de solution toute faite.
Ma méthode: On recherche dans l'expression 73a+97b les couples (a,b) tels que chacun d'eux donnent un résultat différent modulo 31. On choisit 31 pour rechercher tous ses restes car 31 est le plus petit, il y a moins de restes à calculer par rapport à 73 ou 97. Quand on aura trouvé les 31 couples (a,b), toutes les sommes seront disponibles, car à partir du couple (a,b) correspondant au nombre modulo 31, il suffira d'ajouter autant de 31 que nécessaires pour obtenir un nombre voulu. Pour trouver les (a,b), on établit un petit tableau d'additions a\b modulo 31. On n'est pas obligé de faire un tableau 31*31, heureusement: comme il y a 31 résultats différents, on commence par un tableau le plus près de 31 en nombre de cases, soit (6,5) quitte à trouver les restes manquants à la main. On choisit pour a une valeur plus forte que pour b, car 73 est plus petit que 97, car on recherche avant tout un 73a+97b minimum.
Soit ce tableau 6\5: a\b 0 1 2 3 4 0 0 4 8 12 16 1 11 15 19 23 27 2 22 26 30 3 7 3 2 6 10 14 18 4 13 17 21 25 29 5 24 28 1 5 9 Ce tableau se construit rapidement par addition une fois qu'on a rempli les colonnes (a,0) et (0,b).
On a ici de la chance, toutes les valeurs sont différentes et il ne manque que le 20. On l'obtient facilement en regardant le tableau et en cherchant la valeur min pour laquelle on l'obtient: (0,5)
La valeur maximale pour laquelle on obtient tous les restes modulo 31 est représentée par le couple (5,4) qui vaut 5*73+4*97=753=9 modulo31. Toutes les autres valeurs modulo 31 sont obtenues avec des nombres plus petits. Le 2ème nombre le plus grand après 753 est (4,4)=4(73+97)=680. Tous les nombres compris entre 753 et 753 -30 sont donc aussi représentés. Car 752=8 mod31=0*73+2*97+31k (cf tableau) car 751=7 mod31=2*73+4*97+31j ..... Le premier nombre non constructible est donc 753-31=722.
Comme je l'ai dit, le tableau d'addition modulo 31 s'est idéalement présenté (bien que les 3 nombres premiers aient été choisis au hasard). Mais ce ne sera pas toujours aussi facile: imaginons qu'on choisisse 31, 31+8=39, 3*31+8=101. En construisant le tableau d'addition, on aura pour (39k,0):8,16,24,... et pour (0,101k)=8,16,24,...Donc c'est mal parti pour trouver les 31 restes différents de la division par 31. Il faudra aller chercher plus loin dans le tableau pour les trouver tous. On peut même se demander si on n'est pas ramené au même résultat qu'avec 31 et 39 seuls... Donc impossible d'établir de règle.
Si on a plus de 3 nombres, aligner les restes modulo le plus petit et faire son "marché" par addition pour trouver toutes les valeurs.
Merci aux participants qui ont permis de confirmer le nombre que j'avais obtenu.
#19 - 07-01-2013 21:01:52
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
on ne peut pas tout achetzr.
Vraiment bravo, nodgim, pour ton efficace méthode. Je m'étais contenté, comme beaucoup, d'un tableur.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |