Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 04-01-2013 10:26:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

On ne peut pas ttout 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...



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 04-01-2013 11:41:18

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

On nee peut pas tout acheter.

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 : 1945
Lieu: Paris

n ne peut pas tout acheter.

J pas compris et c quoi les variables roll ...
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 : 1374
Lieu: Coutiches

On ne peut pas tout acehter.

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 : 1374
Lieu: Coutiches

On ne peut pas tout ahceter.

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 : 2953

on ne peut pas tout acherer.

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 : 679

nO ne peut pas tout 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 : 2953

On ne peut pas tout acheeter.

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 pas toit 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 : 679

On ne peut pas tout achetr.

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 : 2953

on nr peut pas tout 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 : 1105
Lieu: Jacou

On ne peut pas tout achetr.

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 : 1746

On ne peut pas tout accheter.

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 : 2705
Lieu: Luxembourg

Onn 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 : 1105
Lieu: Jacou

On ne peut pas tout acheteer.

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

 #16 - 07-01-2013 17:42:15

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

on ne peut pas tout avheter.

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 : 1105
Lieu: Jacou

on ne peut pas rout acheter.

OK désolé et merci pour ta clarification. J'étais un peu surpris smile

 #18 - 07-01-2013 18:55:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

On ne peut pas tot acheter.

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 : 2705
Lieu: Luxembourg

On ne peut pas totu acheter.

Vraiment bravo, nodgim, pour ton efficace méthode.
Je m'étais contenté, comme beaucoup, d'un tableur.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete