Concours de talent

[anthonime]

Bonjour à tous,


Dans un concours de talent, un nombre C de candidats sont en compétitions. Ils sont jugés par J juges.
Chaque juge doit choisir un seul candidat comme étant celui qu'il juge le meilleur.
Ainsi, pour simplifier, si l'on prend 4 candidats et 10 juges (C=4 et J=10), on peut avoir comme résultats: {10,0,0,0} (tous les juges ont choisi le même candidat) ou bien {3,0,3,4}, etc...
Les réponses qu'on cherche et qu'on n'arrive pas à formaliser sont:
- combien y a t il de combinaisons possibles de ce type ?
- combien de combinaisons donnent lieu à un seul gagnant ? Ex: {4,3,3,0} est ok (1 candidat gagnant) mais pas {4,4,2,0} (2 candidats ex aequo)
- parmi toutes les combinaisons donnant lieu à un seul gagnant, combien en moyenne de juges ont votés pour le candidat gagnant ?

J'ai essayé de mettre en équation le problème:
si l'on pose Xi le nombre de juges qui votent pour le candidat i (i entre 1 et C), on a:
- Somme(Xi) = J
mais dès lors, connaissant cette contrainte, je n'arrive plus à exposer mon problème en terme d'arrangements ou de combinaisons...

Pourriez vous m'indiquer une piste de réflexion ?
merci beaucoup !

Anthoni

[Luc]

Salut,

pour la première question, que penses-tu de l'ensemble des fonctions de {1,...,J} dans {1,..C}?

[anthonime]

Salut,

pour la première question, que penses-tu de l'ensemble des fonctions de {1,...,J} dans {1,..C}?

Bonjour Luc,

Merci pour ton coup de pouce. Grâce à toi, je me suis aperçu qu'il s'agit plus particulièrement de l'ensemble des surjections de de l'ensemble J (de cardinal j) dans l'ensemble C (de cardinal c).
J'ai trouvé cette page: http://forums.futura-sciences.com/mathematiques-superieur/45497-demonstration-nombre-de-surjections.html qui donne une formule pour trouver ce nombre.
(au passage je me rends compte qu'il s'agit d'un problème de prépa qui porte sur un cours que je n'ai malheureusement pas étudié...)
Cela dit, ceci n'est que le début de la solution, car en fait, si j'arrive à trouver le nombre de surjections possibles, je ne trouve pas le nombre de combinaisons distinctess que ces surjections engendrent...
Pour s'en rendre, réduisons le problème au cas particulier où Card(C)=1.
Point n'est besoin de formules pour se rendre compte qu'il n'existe qu'une seule fonction de {1,...,J} dans {1}. Cette fonction prend chaque élément de J pour les mettre dans l'unique élément de C. Mais cette fonction engendre J combinaisons différentes (une combinaison par élément de J).
Donc, je ne comprends pas en quoi trouver le nombre de surjections de J dans C va me faire avancer ?

Par contre, j'ai finalement trouvé l'exacte réponse à mon problème, grâce à un outil qui s'appelle la "partition d'un entier": http://fr.wikipedia.org/wiki/Partition_d%27un_entier
Mon problème revient donc à trouver le nombre de partitions possible de mon nombre de juges J !
Et l'article donne la formule pour trouver le nombre de combinaisons (ou partitions) :
http://fr.wikipedia.org/wiki/Partition_d%27un_entier#S.C3.A9rie_de_Rademacher

Reste que la formule est sacrément difficile à appliquer...

[Luc]

Salut,

ce problème est très intéressant et redoutablement difficile, j'invite le maximum de participants au forum a participer a ce fil.
Tu es sûr qu'il s'agit des surjections? OK pour la formule de récurrence que tu donnes, mais pour moi il ne s'agit pas des surjections.

Effectivement, deux fonctions de {1,..,J} dans {1,...,C} différentes peuvent correspondre a la même combinaison puisque si je comprends bien, on ne s’intéresse pas a quel juge a choisi tel candidat mais au nombre de juges ayant choisi un candidat donné. Donc si est une permutation de {1,...,J}, et correspondent a la même combinaison.

Si l'on note n_1,...,n_i, ... ,n_C le nombre de juges qui ont choisi le candidat n_i , une combinaison est exactement la donnée du C-uplet (n_1,...,n_C). On impose n_i >=0 (pas de vote négatif) et n_1+....+n_C=J (les juges choisissent un seul candidat, donc le nombre total de choix est égal au nombre de juge).
Le cardinal de l'ensemble de tels C-uplets est exactement, comme tu l'as dit, celui des partitions de l'entier J avec C termes. Notons ce cardinal P(J,C). Je ne sais pas s'il existe une formule explicite pour le calcul de P(J,C). En revanche, on a la formule de récurrence (cf wikipedia). Cette formule permet de calculer aisément P(J,C) par un algorithme récursif avec une complexité raisonnable.
Il est intéressant de regarder la somme de C=1 a C=J des P(J,C). Ces nombres sont appelés nombre de partitions d'un ensemble a J éléments et notes P(J). On peut montrer que ce nombre est égal au nombre de classes de conjugaison du groupe des permutations d'un ensemble a J éléments.

Pour la question 2 (un seul gagnant), il s'agit de partition avec contrainte, ça peut se calculer en fonction des précédents.
Pour la question 3, je ne sais pas. Il faut essayer de faire une moyenne.
Questions bonus : que se passe-t-il si les juges ne choisissent plus un candidat, mais attribuent K points repartis de façon arbitraire entre les candidats? Que se passe-t-il si les juges ont droit a un vote négatif qui pénalisent le candidat d'une voie? Que se passe-t-il si l'on introduit une hiérarchie sur les juges (le vote de certains est plus important que celui d'autres)?

La théorie sous-jacente est la théorie des Tableaux de Young, mais ça dépasse mon niveau de connaissances

[Doraki]

Bonjour à tous,
- combien y a t il de combinaisons possibles de ce type ?

En imaginant que tu tries les juges selon leur votes et que tu mets des barrières pour délimiter les groupes qui votent pour des candidats différents, combien y a-t-il de manières d'arranger 10 juges et 3 barrières ?

[Luc]

En imaginant que tu tries les juges selon leur votes et que tu mets des barrières pour délimiter les groupes qui votent pour des candidats différents, combien y a-t-il de manières d'arranger 10 juges et 3 barrières ?

C'est une méthode de dénombrement due a Bose (le même que celui de Bose-Einstein) je crois.

[anthonime]

Merci Luc pour votre intérêt.

Quelques remarques préalables:
Il existe belle et bien une formule explicite pour le calcul des P(J,C), elle se trouve dans la page wikipedia sous la mention "Série de Rademacher". Mais je suis bien incapable de l'appliquer car je ne comprends pas la notation de la somme dans le terme Ak(n). Si vous pouvez m'éclairer ?

Pour l'heure, donc, j'ai implémenté l'algorithme par récurrence (oui je suis développeur de profession :) soufflé dans l'article et que vous mentionnez également.
Vous dites qu'il est intéressant de regarder la somme de C=1 a C=J des P(J,C), et pour sûr ! C'est précisemment ce que je recherche: en effet, mettons que j'ai 5 juges et 4 candidats, les partitions qui m'intéressent sont {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1}, et {2,1,1,1}.
Cela dit je n'ai pas compris votre phrase : " ce nombre est égal au nombre de classes de conjugaison du groupe des permutations d'un ensemble a J éléments"
Quoiqu'il en soit, le premier problème est réglé. Pour info, si j'ai 2001 juges qui votent pour 4 candidats, j'obtiens p(2001,1) + p(2001,2) + p(2001,3) + p(2001,4) = 56 056 890 (plus que 56 millions de combinaisons possibles !!).

Pour la 2ème question, en revanche, je vous trouve assez expéditif: ces partitions avec contraintes, comment les dénombrer sans les énumérées toutes ???

Si vous pouviez m'éclairer également, cela m'aiderait.

Merci beaucoup.

[anthonime]

Bonjour Doraki,

Je ne vois pas où vous voulez en venir... Etes vous sûr qu'on parle du même problème ?

[Luc]

La série de Rademacher est explicite, mais elle est très complexe (c'est le cas de la dire) puisqu'elle fait intervenir la théorie des fonctions de variable complexe, et je ne pense pas qu'il soit facile de l’implémenter.
Mais dans le cas présent on n'a pas besoin d'une formule explicite, un algorithme suffit.

Le candidat 1 est gagnant si et seulement si les candidats 2,...,C, ont un nombre de voies strictement inférieur. Autrement dit, si n_2,...,n_C forment une partition de J-n_1 en C-1 parties inférieures ou égales a n_1-1. Mais je m’aperçois que la contrainte complique le problème. En effet, on peut montrer que le nombre de partitions de J dont la plus grande partie est m est égal au nombre de partitions de J en m parties. En revanche je ne sais pas s'il y a un résultat analogue pour le nombre de partitions de J en C parties dont la plus grande partie est imposée.

Peut être faut-il dénombrer le complémentaire, a savoir le nombre de combinaisons avec au moins deux gagnants?

Pour la question de moyenne, je ne sais pas... peut être faire l’expérience avec des petites valeurs pour émettre une conjecture.