Archi classique...

par **Ben314** » 07 Fév 2010, 13:29

Au cas ou certain ne connaitraient pas ce joli problème archi classique :

Dans un club de ping-pong, on décide d'organiser un tournoi par éliminations. Comme on ne sait pas trop le nombre de participants qui vont se présenter, on établi la règle suivante :
- Le tournoi se déroulera en "tours".
- A chaque tour, on tire au hasard des rencontres entre deux joueurs (chaque joueur participe a une et une seule rencontre) et seuls les gagnant participent au tour suivant.
- Comme il y a un problème lorsqu'un tour doit être organisé avec un nombre impair de joueurs, on décide que, dans ce cas, un des joueurs tirés au hasard ne participera a aucune rencontre et participera quand même au tour suivant.

Sachant qu'en fait 1025 participants se sont présentés au tournoi, combien de matchs ont été joués ?

P.S. : le but est non seulement de trouver une solution, mais plutôt de trouver une "jolie" solution généralisable à un nombre quelconque de joueurs...

par **ffpower** » 07 Fév 2010, 13:45

Je pense que t as été gentil avec 1025=2^10+1..C'est facile de voir a la main du coup..

par **Ben314** » 07 Fév 2010, 13:46

ffpower a écrit:Je pense que t as été gentil avec 1025=2^10+1..C'est facile de voir a la main du coup..

On va dire que c'est un peu... pour tromper le client... :marteau:

par **ffpower** » 07 Fév 2010, 13:49

oui ok lol..
Bon ben dsl d avoir gaché le truc du coup :)

par **nodgim** » 07 Fév 2010, 13:54

Je ne connaissais pas mais c'est drôle.
On écrit le nombre de participants en binaire.
Chaque 1 du nombre représente 2 puissance (nb de chiffres à droite) -1 matches. On additionne et c'est fini.

par **Ben314** » 07 Fév 2010, 14:06

C'est O.K., mais il y a une autre solution beaucoup plus simple...
Regarde ce que donne ta soluce pour quelques entiers tirés au hasard...

par **nodgim** » 07 Fév 2010, 14:29

On retire le nombre de 1 du binaire.

par **Ben314** » 07 Fév 2010, 14:31

nodgim a écrit:On retire le nombre de 1 du binaire.

La fin de la phrase ("du binaire") n'est pas... indispensable.
Au vu du résultat, ne vois tu pas une autre preuve (sans passer en binaire...) ?

par **nodgim** » 07 Fév 2010, 16:28

Dit autrement, on retire 1 à chaque résultat impair dans la suite des divisions succesives par 2.

par **ffpower** » 07 Fév 2010, 16:38

T obtiens avec 175 participants par exemple?

par **nodgim** » 07 Fév 2010, 16:51

169 matches, pourquoi ?

par **ffpower** » 07 Fév 2010, 16:54

tu t es trompé alors..

par **nodgim** » 07 Fév 2010, 17:08

ffpower a écrit:tu t es trompé alors..

Zut, j'ai donné le résultat quand le joueur éliminé ne joue plus du tout.
Si le joueur en trop joue le tour suivant, ça fait donc nombres de matches=nombres de joueurs -1.
Il y en a au moins 1 qui suit ce soir.

par **Imod** » 07 Fév 2010, 18:21

Bonsoir

Si je ne m'abuse , on élimine exactement un joueur à chaque match , le résultat est donc complètement trivial :)

Imod

par **Ben314** » 07 Fév 2010, 18:34

Imod a écrit:Bonsoir
Si je ne m'abuse , on élimine exactement un joueur à chaque match , le résultat est donc complètement trivial
Imod

Tout à fait thierry, tout à fait...

par **maxence6** » 11 Fév 2010, 10:14

Je trouve par exemple pour:
-5 joueurs 4 matchs
-6 joueurs 5 matchs
-3 joueurs 2 matchs

Exemple pour 6 joueurs:

6 joueurs on divise en autant de paquets de deux que possible
donc 3 paquets de 2, les trois paquet de deux donnent chacun un vainceur donc il reste 3 joueurs. 1 paquets de 2 plus 1 le paquet de 2 donne un vainceur qui joue contre celui qui reste sa fait 5 matchs !

par **ffpower** » 11 Fév 2010, 10:24

Lis plutot la solution d imod ci dessus

Archi classique...

Archi classique...

Qui est en ligne