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
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Retour

Résumé de la discussion

nodgim
04-05-2012 18:19:06

Si n nombres dans la liste, le maximum de sommes différentes que tu peux faire est 2^n -1. C'est un max compte tenu des possibles redondances.

Sinon, pour trouver un S donné, c'est un peu la même démarche que pour trouver si un nombre est premier. Je ne vois pas trop de possibilités de raccourcis. Beau problème en tout cas.

Klimrod
03-05-2012 18:56:13

Si S est plus petit que le plus petit des éléments de la liste ! cool

Ah zut ! je n'avais pas vu qu'on était dans les entiers relatifs...
Bon je m'en vais...
Klim.

shadock
03-05-2012 18:17:05

Si S est un nombre premier somme d'un nombre pair d'éléments et que les éléments sont une suites de nombres premiers amicaux.

Si S est premier, on élimine les nombres pairs, les sommes de 2N éléments impairs  et certainement d'autres critères mais c'est tout ce que j'ai en tête.

Shadock

Clydevil
03-05-2012 08:53:53

Hello,

Je m'intéresse au probleme suivant:
-On fournit une liste finie d'entiers (positif ou négatif)
-Ainsi qu'une somme S, un entier également.
-Le but étant de déterminer si on peut ou non obtenir S par sommation d'une partie des entiers données.

Remarque sur le probleme:
C'est une de nombreuse variante du probleme du sac à dos. Cette variante est NP-complete etc...  (donc bon bref on ne trouvera rien de trivial pour répondre a la question).

Personnellement je m'intéresse à tous les criteres rapidement calculables (en temps polynomial) permettant de déduire qu'on ne peut pas obtenir S.

Par exemple:
-Si S est strictement plus grand que la somme de tous les entiers positifs de la liste il est claire qu'on aura aucune chance d'obtenir S. (de la même manière strictement inférieur, entier négatif etc...)
-Après il y a des criteres de divisibilité du genre si S est impair et que tous les éléments de la listes sont pairs, idem on peut conclure que c'est impossible.
Ce dernier critère peut légèrement s'élargir: On choisit un entier k, on calcule le modulo k de chaque entier de la liste et de la somme, si le modulo de la somme est strictement plus grand que la somme des modulo des éléments de la liste on ne pourra pas obtenir S.

Et vous à quels critères pensez vous? Citez n'importe quel cas particuliers vous permettant de rapidement conclure qu'on ne peut pas obtenir S.

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