100 urnes à trier

[Imod]

Bonsoir :zen:

Trois problèmes pour le prix d'un , les deux premiers sont déjà bien amusants et le troisième est un vrai casse-tête :marteau:

1°) 99 urnes contiennent des boules bleues et des boules rouges . Montrer que l'on peut choisir 50 de ces urnes de façon à ce qu'elles contiennent au moins la moitié des boules bleues et la moitié de boules rouges .
2°) 100 urnes contiennent des boules bleues et des boules rouges . Montrer que l'on peut choisir 34 de ces urnes de façon à ce qu'elle contiennent au moins un tiers des boules bleues et un tiers des boules rouges .
3°) 100 urnes contiennent des boules bleues , des boules blanches et des boules rouges . Montrer que l'on peut choisir 51 de ces urnes de façon à ce qu'elles contiennent au moins la moitié des boules bleues , la moitié des boules blanches et la moitié des boules rouges .

Amusez-vous bien :zen:

Imod

[ffpower]

Je parie que c est un principe des tiroirs lol.

[Imod]

Je parie que c est un principe des tiroirs lol.

Combien ? Je suis un peu à court en ce moment :we:

Imod

[nodgim]

Pour la question 1)
On met de coté l'urne contenant le plus de bleues. On partage en 2 tas de 49 les autres urnes de telle sorte que le nombre de bleues soit égal ou très proche de chaque coté. l'urne de réserve sera alors mise d'un coté ou de l'autre.

[Imod]

Pas mal du tout nodgim :++:

Il reste à affiner un tout petit peu ta stratégie en supposant par exemple que les urnes sont initialement classées de celle qui contient le plus de bleus à celle qui en contient le moins . Sinon l'idée est là !!!

Imod

[ffpower]

J ai reussi de mon coté le 1 en faisant une double reccurence(nb d urnes+nb de boules).Ce qui fait donc une demo un peu foireuse lol

[nodgim]

Pas mal du tout nodgim :++:

Il reste à affiner un tout petit peu ta stratégie en supposant par exemple que les urnes sont initialement classées de celle qui contient le plus de bleus à celle qui en contient le moins . Sinon l'idée est là !!!

Imod

C'est volontairement que j'ai donné une solution avec des trous, pour laisser un peu de mystère à ceux qui s'y intéressent. :++:

[Imod]

La méthode que je connais est constructive et ne procède pas par récurrence ou induction .

Imod

[ffpower]

Depuis quand une reccurence n est pas constructive?ca donne un algorithme(p-e un peu plus compliqué que le tien soit,mais c est tout..)

[Imod]

La méthode que je connais est constructive et ne procède pas par récurrence ou induction .

Imod

Je voulais simplement dire qu'une fois les boîtes rangées choisir les bonnes est quasi-instantané :we:

Imod

[Imod]

Bon , je donne une réponse pour le premier problème histoire de remotiver les troupes !

On suppose que les urnes sont classées par ordre décroissant de boules bleues . On prend alors l'urne puis parmi et « celle » qui contient le plus de boules rouges puis parmi et « celle » qui contient le plus de boules rouges ... puis parmi et « celle » qui contient le plus de boules rouges . Il est clair qu’on a pris plus de boules rouges qu’on en a laissé et si on note le nombre de boules bleues dans l’urne , dans le pire des cas on a pris boules bleues . Or , on a donc pris au moins la moitié des bleues .

Reste les deux autres problèmes …

Imod

[ffpower]

C est plus joli que ma pseudo reccurence lol(qui en plus ne marche pas pour les autres questions).Bon,pour le 2,la meme solution marche non(en faisant des groupes de 3)?

[Imod]

Bon,pour le 2,la meme solution marche non(en faisant des groupes de 3)?

Oui , et bon courage pour le 3 :doh:

Imod

[nodgim]

Bon , je donne une réponse pour le premier problème histoire de remotiver les troupes !

On suppose que les urnes sont classées par ordre décroissant de boules bleues . On prend alors l'urne puis parmi et « celle » qui contient le plus de boules rouges puis parmi et « celle » qui contient le plus de boules rouges ... puis parmi et « celle » qui contient le plus de boules rouges . Il est clair qu’on a pris plus de boules rouges qu’on en a laissé et si on note le nombre de boules bleues dans l’urne , dans le pire des cas on a pris boules bleues . Or , on a donc pris au moins la moitié des bleues .

Reste les deux autres problèmes …

Imod

Tiens j'avais fait plus simple! :doh:
Je garde par devers moi le plus gros bleu. Je trie les autres bleus du plus gros au plus petit. Je prends alors les bleus 2 par 2 et j'équilibre au mieux. A la fin, je regarde où est la majorité des rouges, et je mets le gros bleu de réserve dans la moitié majoritaire rouge.

[ffpower]

en effet,soit le tas U1,U3,U5....,U99 marche,soit le tas U1,U2,U4...,U98 marche
Edit:faut plus que tu postes nodgim,666 messages c est classe.
Edit2:ah ben trop tard,tant pis lol

[nodgim]

Un essai pour le 3)
Je trie les bleus et les rouges, je ne m'occupe pas des blancs.
Je vérifie d'abord qu'il n'y a pas un tiroir qui à lui seul contiendrait plus de la moitié de tous les autres dans une couleur donnée. La stratégie serait alors facilitée, mais il faudrait procéder autrement.
Donc je prends les 2 plus gros bleus et je les mets chacun dans un des 2 tas que je vais constituer. Je prends ensuite les 2 plus gros rouges et je fais le choix en fonction des bleus qui les accompagnent, car c'est eux qui en principe auront le plus gros écart. Je prends ensuite les 2 plus gros bleus et je fais le même choix que précédemment. En procédant ainsi, j'aurais bien à la fin au moins un tiers de bleus et de rouges dans chaque tas. Ensuite, il ne reste qu'a choisir le tas qui comporte au moins un tiers de blancs.

[nodgim]

en effet,soit le tas U1,U3,U5....,U99 marche,soit le tas U1,U2,U4...,U98 marche
Edit:faut plus que tu postes nodgim,666 messages c est classe.
Edit2:ah ben trop tard,tant pis lol

Bah, tout le monde est passé par là un jour ou l'autre :happy2:
Qu'espérer maintenant, comme nombre remarquable ? 1729, par exemple ?

[Imod]

nodgim ,

pour le 3) je ne vois pas comment tu arrives à avoir assez de blanc et de bleus vu que tu donnes priorité aux rouges sur le dernier choix ( il en faut 1/2 et pas 1/3 ) ?

Imod

[nodgim]

Je ne donne pas spécialement priorité aux rouges, mais alternativement aux rouges et aux bleus. Un exemple:
Je prends les 2 plus gros bleus: (100B 25R) (95B 78R)
Je prends les 2 plus gros rouges: (90R 3B) (90R 56B)
Je groupe selon la moindre différence TOTAL: (103B,115R)(98B,168R)

Je prends à nouveau les 2 plus gros bleus: (94B, 13R) (93B, 88R)
Je groupe selon la moindre différence:
TOTAL: (196B, 203R) (192B, 181B)
Je prends les 2 plus gros rouges, etc..
En fait je vise à l'équilibre, pour être sûr d'avoir au moins 1/3 de chaque coté.
Ensuite il n'y plus à la fin qu'à choisir le coté majoritaire blanc.

Gros problème avec cette méthode: aucun moyen de quantifier au final la proportion exacte des bleus et des rouges de part et d'autre. En particulier, aucun moyen de vérifier que le 1/3 est atteint. Avec 100 urnes, ça semble assez évident, mais....

[Imod]

Je t'avais bien compris nodgim , je parlais du dernier choix :we:

Gros problème avec cette méthode: aucun moyen de quantifier au final la proportion exacte des bleus et des rouges de part et d'autre. En particulier, aucun moyen de vérifier que le 1/3 est atteint. Avec 100 urnes, ça semble assez évident, mais....

Je te rappelle que ce n'est pas 1/3 mais 1/2 qu'il faut atteindre :marteau:

Imod