Avis aux pros des équations — Les-mathematiques.net The most powerful custom community solution in the world

Avis aux pros des équations

Bonjour,
J'ai une liste de 100 nombres divers. Je veux que la somme des 50 nombres pairs (2e nombre, 4e nombre...) soit égale à la somme des 50 nombres impairs (1er nombre, 3e nombre...).

Pour que cette relation soit vraie il faudrait bien une équation à 100 inconnues?

Merci

Réponses

  • Ton problème se traduit par une équation à $100$ inconnues oui. Au passage tu veux parler des nombres en position paire/impaire, et pas des nombres pairs/impairs.
  • Oui et non.
    Tu as 100 nombres.. Autrement dit, tu as 100 jetons avec un nombre marqué dessus. Tu veux faire 2 groupes, pour que la somme soit la même pour chacun des 2 groupes.
    Ca donne bien une équation avec 100 inconnues.
    Mais ça te donne aussi 100 'contraintes', très utiles (les 100 inconnues doivent se répartir les 100 valeurs des 100 jetons). Et ces 100 contraintes là sont très difficile à traduire en équations.

    Ton problème est un petit peu un problème d'équations, mais surtout un problème de combinatoire.
  • Merci pour vos réponses.
    Oui c'est bien la position des nombres qui est paire/impaire.

    Donc si je comprends bien c'est quasi impossible à résoudre.
    Cordialement.
  • Ca se résout par tâtonnements, pas par équations.
    Tu divises tes 100 jetons en 2 groupes de 50, tu calcules le total obtenu pour chacun des 2 groupes.
    Puis tu essaies de trouver un jeton dans chaque groupe, pour pouvoir réduire l'écart en permutant ces 2 jetons.

    Il faut vraiment voir le problème comme 2 groupes de 50 jetons. Ensuite, disposer un groupe aux positions paires, dans n'importe quel ordre, et l'autre groupe aux positions impaires, dans n'importe quel ordre, ce n'est pas un problème.

    Si les jetons portent des numéros à peu près similaires (par exemple tous les jetons ont un nombre entre 100 et 300), alors on trouve assez vite une solution. Quand l'écart est de 10, on a toutes les chances de trouver une paire de jetons qui va ramener l'écart à 0.

    Mais si les jetons portent des numéros très dispersés, (par exemple tous les jetons ont un nombre entre 10000 et 20000) alors, quand l'écart est de 10, trouver une paire de jetons qui va ramener l'écart à 0, ça tient du miracle.

    Et dans ce cas, il ne faut plus tâtonner, il faut utiliser un programme qui va tester toutes les dispositions.
  • Avec les nombres 1,2,3,4,...99, 100000, ce n'est pas possible.

    Cordialement.
  • Salut.

    Une équation à 100 inconnues ; tu as une infinité de solutions.
  • Bonjour,

    Il me semble que c’est un problème très facile et non pas impossible.

    On a une combinaison finie de configurations. On les essaie toutes. Si une ou plusieurs solutions existent, on les trouve toutes.

    Problème suivant ?
  • YvesM,

    tu as vraiment essayé "Avec les nombres 1,2,3,4,...99, 100000" ?
    Laisse tomber, j'ai mal lu ta réponse.

    Cordialement.
  • Ça c'est la théorie. Et en pratique comment vas-tu trouver une solution optimale à un grand problème de programmation linéaire en nombres entiers en un temps raisonnable? ( disons en moins de 10 ans)
    Pour information il y a $100\choose 50$ façons de choisir 50 nombres parmi 100 soit
    $100\choose 50$ couples de sommes de 50 nombres. Épuiser toutes les possibilités prend trop de temps, il faut pour le faire trouver un algorithme spécifique ou à défaut des heuristiques pertinentes.
  • On résout le programme linéaire en nombre entiers sous les contraintes :
    $$
    \begin{cases}
    \displaystyle \sum_{p=0}^{49}x_{2p+1}=\sum_{p=1}^{50}x_{2p}\\
    x_{\min}\leq x_i\leq x_{\max}\\[1mm]
    x_i\in\mathbb{N}\cup\lbrace -\infty\rbrace
    \end{cases}
    $$ par la méthode des coupes de Gomory après avoir déterminé les données $x_{\min}$ et $x_{\max}$. Cela consiste à résoudre le programme linéaire en nombres réels et à rajouter des contraintes d'intégrité chaque fois qu'une variable solution de l'optimum n'est pas entière, on pourra consulter
    cette référence
    La fonction de coût à maximiser est $\sum_{i=1}^{100}x_i$ en initialisant toutes les variables à $-\infty$ pour signifier qu'elles ne sont pas encore affectées et en posant $\forall n\in\mathbb{N},\ n+(-\infty)=-\infty$.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!