Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
175 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Avis aux pros des équations

Envoyé par Mathco 
Avis aux pros des équations
il y a trois mois
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
Re: Avis aux pros des équations
il y a trois mois
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.
Re: Avis aux pros des équations
il y a trois mois
avatar
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.
Re: Avis aux pros des équations
il y a trois mois
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.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Avis aux pros des équations
il y a trois mois
avatar
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.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Avis aux pros des équations
il y a trois mois
Avec les nombres 1,2,3,4,...99, 100000, ce n'est pas possible.

Cordialement.
Re: Avis aux pros des équations
il y a trois mois
avatar
Salut.

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

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''
Re: Avis aux pros des équations
il y a huit jours
Re: Avis aux pros des équations
il y a huit jours
avatar
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 ?
Re: Avis aux pros des équations
il y a huit jours
YvesM,

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

Cordialement.



Edité 1 fois. La dernière correction date de il y a huit jours et a été effectuée par gerard0.
Re: Avis aux pros des équations
il y a huit jours
Ç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.



Edité 2 fois. La dernière correction date de il y a cinq jours et a été effectuée par AlainLyon.
Re: Avis aux pros des équations
il y a deux jours
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$.

Je pourrais être plus précis si mon salaire de misère était plus élevé.



Edité 10 fois. La dernière correction date de il y a deux jours et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 692, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page