Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

Partagez
 

 Est-ce que l'algorithme glouton l'emporte?

Aller en bas 
AuteurMessage
mathman
Modérateur


Masculin Nombre de messages : 967
Age : 30
Date d'inscription : 31/10/2005

Est-ce que l'algorithme glouton l'emporte? Empty
MessageSujet: Est-ce que l'algorithme glouton l'emporte?   Est-ce que l'algorithme glouton l'emporte? EmptyDim 25 Mar 2007, 17:31

On se donne un réel k tel que 0 <= k <= 1/2.

Considérons n nombres positifs ou nuls écrits sur un tableau. En un mouvement, on peut effacer deux nombres a et b du tableau, et les remplacer par le nombre k(a+b). Après n-1 mouvements, il ne reste plus qu'un seul nombre au tableau; appelons ce nombre r.

Pour un nombre quelconque n de nombres initialement écrits au tableau, quels mouvements doivent être effectués afin d'obtenir la plus petite valeur possible de r?

Je conjecture qu'à chaque mouvement, on doit choisir pour a et b les deux plus grands des nombres présents au tableau. C'est une sorte d'algorithme glouton et il est plausible intuitivement qu'il fournisse le r minimal. Mais quelqu'un a-t-il une preuve?

Le problème est inspiré par une question d'Arthur Engel, qui demande de montrer que r >= 1/n pour k = 1/4.
Revenir en haut Aller en bas
elhor_abdelali
Expert grade1
elhor_abdelali

Masculin Nombre de messages : 461
Age : 56
Localisation : Maroc.
Date d'inscription : 24/01/2006

Est-ce que l'algorithme glouton l'emporte? Empty
MessageSujet: Re: Est-ce que l'algorithme glouton l'emporte?   Est-ce que l'algorithme glouton l'emporte? EmptyDim 25 Mar 2007, 19:11

Bonjour mathman ;
Je crois que le k doit être strictement inférieur à 1/2
car sinon ta conjecture risque de ne pas aboutir ,
Prendre par exemple le tableau de nombres : 1 , 2 , 3 , 5
en remplaçant les deux plus grands (3 et 5) par leur moyenne
on a le nouveau tableau : 1 , 2 , 4 , 4
et à partir de là ça devient stationnaire farao (sauf erreur bien entendu)
Revenir en haut Aller en bas
http://www.ilemaths.net/forum_superieur-4.php
mathman
Modérateur


Masculin Nombre de messages : 967
Age : 30
Date d'inscription : 31/10/2005

Est-ce que l'algorithme glouton l'emporte? Empty
MessageSujet: Re: Est-ce que l'algorithme glouton l'emporte?   Est-ce que l'algorithme glouton l'emporte? EmptyDim 25 Mar 2007, 20:23

Ah oui je vois.
En fait je réalise qu'il manque un truc dans mon énoncé.

Citation :
Considérons n nombres positifs ou nuls écrits sur un tableau. En un mouvement, on peut effacer deux nombres a et b du tableau, et les remplacer par le seul nombre k(a+b). Après n-1 mouvements, il ne reste plus qu'un seul nombre au tableau; appelons ce nombre r.

J'ai juste rajouté le mot "SEUL".

Du coup dans ton exemple, avec k = 1/2, on aurait 1, 2, 4 en fait.
Revenir en haut Aller en bas
mathman
Modérateur


Masculin Nombre de messages : 967
Age : 30
Date d'inscription : 31/10/2005

Est-ce que l'algorithme glouton l'emporte? Empty
MessageSujet: L'algorithme glouton l'emporte! :)   Est-ce que l'algorithme glouton l'emporte? EmptyDim 01 Avr 2007, 12:53

J'ai résolu ce problème je crois.
Par contre il faudra que je formalise tout ça et ça ne sera pas facile.

Evidemment, si quelqu'un est intéressé, je peux poster l'esquisse de ma preuve.
Revenir en haut Aller en bas
Contenu sponsorisé




Est-ce que l'algorithme glouton l'emporte? Empty
MessageSujet: Re: Est-ce que l'algorithme glouton l'emporte?   Est-ce que l'algorithme glouton l'emporte? Empty

Revenir en haut Aller en bas
 
Est-ce que l'algorithme glouton l'emporte?
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Je veux une histoire à la Autant en emporte le vent!
» algorithme
» Un algorithme écologique
» [Salon] L'algorithme.
» algorithme d arnoldi pour la resolution des systemes lineai

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Combinatoire-
Sauter vers: