Problème 1021
Dans ce pays très en avance sur la démocratie, les élections municipales permettent d'élire dans chaque commune les conseillers de manière très particulière. La taille du conseil municipal, fixée par décret, dépend de celle de la commune. Les candidatures sont individuelles. Une fois le nombre de candidats validé, il est décidé pour combien d'entre eux chaque électeur a l'obligation de voter (ni vote blanc, ni nul ne sont autorisés).Ce choix a pour origine la règle suivante : après le vote, une synthèse est faite par un programme informatique qui détermine le conseil municipal avec une condition qui ne souffre aucune exception : quel que soit le vote des électeurs, chaque électeur y trouvera au moins l'un des candidats pour lesquels il a voté.
Lors des dernières élections, dans la petite ville où habite Alice, afin d'élire 10 conseillers, chaque électeur devait voter pour 10 des 25 candidats.
- 1A. Quel était, au plus, le nombre de votants de la ville d'Alice ?
- 2A. Quel était, au minimum, ce nombre ?
Ce problème m'a occupé plus que tout autre problème, peut-être même que tous les autres problèmes réunis, et pour cause : il est extrêmement difficile. Je n'ai au final pas réussi à le résoudre, mais les organisateurs non plus, et il n'a pas été noté.
Dans la suite, on note :
Voici tout d'abord un programme qui effectue une énumération exhaustive sur des petites valeurs de N et E. La fonction compute_votes_possibles() construit un tableau à 2 dimensions, dont chaque ligne représente un choix de E valeurs parmi N (implanté sous la forme d'un tableau booleén). Ce tableau a donc C(N, E) lignes (nombre de combinaisons de E valeurs parmi N). La fonction explore_vote() est ensuite appelée pour des valeurs de V croissantes jusqu'à ce qu'elle retourne false : dans ce cas, cela indique que quelque soit la combinaison de V votes, et quelque soit les candidats élus, il existe au moins un vote pour lequel aucun des choix de candidat n'est élu. La fonction explore_vote() énumère simplement toutes les combinaisons de votes possibles (il y en a C(C(N, E), V)) puis vérifie la contrainte en question.
Par exemple, pour NB_MAX_ELUS = 6 (valeur max de E), on obtient : (E varie sur la ligne, N sur la colonne)
Regardons certaines de ces valeurs plus en détail. Le cas N < 2 × E est trivial et n'est pas énuméré (il suffit de prendre les E premiers candidats). Les cas N = 2 × E sont faciles également (E = 2, N = 4; E = 3, N = 6) : s'il y a C(N, E) électeurs, alors tous les votes sont possibles, et il y a dans ce cas exactement un vote qui ne respecte pas la contrainte quelque soit le choix des élus. Si en revanche il y a C(N, E) − 1 électeurs, alors tous les votes sauf 1 peuvent être obtenus, et dans ce cas, il suffit de choisir les candidats qui sont le complément de ceux du vote manquant (on observe bien que 5 = C(4, 2) − 1 et que 19 = C(6, 3) − 1. Pour E = 2 et N ≥ 6, on voit bien que le nombre d'électeur maximal est de 2, car avec 3 électeurs, il peut y avoir des votes totalement disjoints.
L'énumération exhaustive ne permet pas tellement d'aller plus loin. Mais on peut déjà observer que la solution des concepteurs est fausse : voici un programme l'implémentant, pour lequel on retrouve bien la valeur de 1358 pour la question 1 (E = 10, N = 25). Pour les valeurs E = 3, N = 7, on observe que la valeur obtenue par la solution des concepteurs (10) est différente de la valeur obtenue par la méthode exhaustive (11).
J'ai ensuite essayé différentes techniques (heuristiques) pour essayer de ne pas revenir sur un vote une fois celui-ci sélectionné (aucune n'a marché). J'en présente une ici : l'idée pour choisir un nouveau vote est de répartir au mieux les voix entre les candidats vis-à-vis des votes déjà existants. Ainsi, on définit la notion de similarité entre 2 votes comme étant le nombre de candidats en commun parmi ces deux votes. Lors du choix d'un vote, on regarde pour tous les votes possibles la similarité avec tous les votes existants, et on choisit celui qui minimise le maximum de similarité. Si ce maximum est atteint par plusieurs votes possibles, on prend celui qui atteint le minimum le moins de fois. Ensuite, s'il y a encore plusieurs votes possibles, on regarde le maximum suivant en répétant le processus.
Ainsi, par exemple, si on considère 5 votes existants et un extrait de 4 votes possibles ayant les similarités suivantes :
2 1 0 1 2
3 1 1 0 1
3 3 0 1 2
0 1 1 2 1
On commence par trier les votes possibles par leur similarité, pour obtenir : 0 1 1 2 2
0 1 1 1 3
0 1 2 3 3
0 1 1 1 2
On parcourt ensuite par colonne (en commençant par celle de droite) et on élimine au fur et à mesure les votes possibles quand leur similarité n'est pas égale au minimum. Dans cet exemple, il reste les votes 2 et 4 quand on regarde la dernière colonne, après quoi seul le vote possible 4 est retenu.
Enfin, quand le nombre de votes existants est faible, plusieurs votes possibles ont les mêmes similarités. On en choisit alors un au hasard. Néanmoins, on se rend compte assez vite que cela ne marche pas et donne une borne supérieure très grossière du nombre de votants (par exemple, pour E = 3 et N = 7, on trouve 17 au lieu de 11).
On peut par ailleurs voir sur un exemple très simple pourquoi cela ne marche pas. Considérons le cas avec E = 2 et N = 5. La recherche exhaustive nous dit que le nombre maximal de votants est 3, alors que l'heuristique au-dessus donne 4. Considérons les deux ensembles de 4 votes suivants : à gauche, un exemple qui montre que 4 électeurs n'est pas possible, à droite, le cas construit par l'heuristique présentée.
On remarque que les 2 4e votes ont la même similarité (1 0 1 et 1 1 0), mais que celui de droite admet une solution (candidats 1 et 3) contrairement à celui de gauche. Je n'ai pas trouvé de critère différenciant ces deux figures.
On peut aussi explorer récursivement tous les votes possibles ayant la similarité minimum quand il y en a plusieurs (cela fait l'hypothèse que la solution optimale respecte ce critère même si elle n'est plus la seule, mais cela n'est même pas sûr), mais les calculs explosent compètement d'un point de vue combinatoire (cela est même plus mauvais que l'exhaustif). On pourrait sans doute trouver des bornes assez proches en testant au hasard quelques votes en haut de l'arbre d'exploration. Le code est ici.
Dans la suite, on note :
- N : le nombre de candidats
- E : le nombre d'élus
- H : le nombre de choix sur un bulletin
- V : le nombre de votants
Voici tout d'abord un programme qui effectue une énumération exhaustive sur des petites valeurs de N et E. La fonction compute_votes_possibles() construit un tableau à 2 dimensions, dont chaque ligne représente un choix de E valeurs parmi N (implanté sous la forme d'un tableau booleén). Ce tableau a donc C(N, E) lignes (nombre de combinaisons de E valeurs parmi N). La fonction explore_vote() est ensuite appelée pour des valeurs de V croissantes jusqu'à ce qu'elle retourne false : dans ce cas, cela indique que quelque soit la combinaison de V votes, et quelque soit les candidats élus, il existe au moins un vote pour lequel aucun des choix de candidat n'est élu. La fonction explore_vote() énumère simplement toutes les combinaisons de votes possibles (il y en a C(C(N, E), V)) puis vérifie la contrainte en question.
Par exemple, pour NB_MAX_ELUS = 6 (valeur max de E), on obtient : (E varie sur la ligne, N sur la colonne)
Max votants pour N et E donnés :
0 1 2 3 4 5
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0 | . . . . . .
1 | . . . . . .
2 | . . . . . .
3 | . . -1 . . .
4 | . . 5 -1 . .
5 | . . 3 -1 -1 .
6 | . . 2 19 -1 -1
7 | . . 2 11 -1 -1
0 1 2 3 4 5
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0 | . . . . . .
1 | . . . . . .
2 | . . . . . .
3 | . . -1 . . .
4 | . . 5 -1 . .
5 | . . 3 -1 -1 .
6 | . . 2 19 -1 -1
7 | . . 2 11 -1 -1
Regardons certaines de ces valeurs plus en détail. Le cas N < 2 × E est trivial et n'est pas énuméré (il suffit de prendre les E premiers candidats). Les cas N = 2 × E sont faciles également (E = 2, N = 4; E = 3, N = 6) : s'il y a C(N, E) électeurs, alors tous les votes sont possibles, et il y a dans ce cas exactement un vote qui ne respecte pas la contrainte quelque soit le choix des élus. Si en revanche il y a C(N, E) − 1 électeurs, alors tous les votes sauf 1 peuvent être obtenus, et dans ce cas, il suffit de choisir les candidats qui sont le complément de ceux du vote manquant (on observe bien que 5 = C(4, 2) − 1 et que 19 = C(6, 3) − 1. Pour E = 2 et N ≥ 6, on voit bien que le nombre d'électeur maximal est de 2, car avec 3 électeurs, il peut y avoir des votes totalement disjoints.
L'énumération exhaustive ne permet pas tellement d'aller plus loin. Mais on peut déjà observer que la solution des concepteurs est fausse : voici un programme l'implémentant, pour lequel on retrouve bien la valeur de 1358 pour la question 1 (E = 10, N = 25). Pour les valeurs E = 3, N = 7, on observe que la valeur obtenue par la solution des concepteurs (10) est différente de la valeur obtenue par la méthode exhaustive (11).
J'ai ensuite essayé différentes techniques (heuristiques) pour essayer de ne pas revenir sur un vote une fois celui-ci sélectionné (aucune n'a marché). J'en présente une ici : l'idée pour choisir un nouveau vote est de répartir au mieux les voix entre les candidats vis-à-vis des votes déjà existants. Ainsi, on définit la notion de similarité entre 2 votes comme étant le nombre de candidats en commun parmi ces deux votes. Lors du choix d'un vote, on regarde pour tous les votes possibles la similarité avec tous les votes existants, et on choisit celui qui minimise le maximum de similarité. Si ce maximum est atteint par plusieurs votes possibles, on prend celui qui atteint le minimum le moins de fois. Ensuite, s'il y a encore plusieurs votes possibles, on regarde le maximum suivant en répétant le processus.
Ainsi, par exemple, si on considère 5 votes existants et un extrait de 4 votes possibles ayant les similarités suivantes :
2 1 0 1 2
3 1 1 0 1
3 3 0 1 2
0 1 1 2 1
On commence par trier les votes possibles par leur similarité, pour obtenir : 0 1 1 2 2
0 1 1 1 3
0 1 2 3 3
0 1 1 1 2
On parcourt ensuite par colonne (en commençant par celle de droite) et on élimine au fur et à mesure les votes possibles quand leur similarité n'est pas égale au minimum. Dans cet exemple, il reste les votes 2 et 4 quand on regarde la dernière colonne, après quoi seul le vote possible 4 est retenu.
Enfin, quand le nombre de votes existants est faible, plusieurs votes possibles ont les mêmes similarités. On en choisit alors un au hasard. Néanmoins, on se rend compte assez vite que cela ne marche pas et donne une borne supérieure très grossière du nombre de votants (par exemple, pour E = 3 et N = 7, on trouve 17 au lieu de 11).
On peut par ailleurs voir sur un exemple très simple pourquoi cela ne marche pas. Considérons le cas avec E = 2 et N = 5. La recherche exhaustive nous dit que le nombre maximal de votants est 3, alors que l'heuristique au-dessus donne 4. Considérons les deux ensembles de 4 votes suivants : à gauche, un exemple qui montre que 4 électeurs n'est pas possible, à droite, le cas construit par l'heuristique présentée.
On remarque que les 2 4e votes ont la même similarité (1 0 1 et 1 1 0), mais que celui de droite admet une solution (candidats 1 et 3) contrairement à celui de gauche. Je n'ai pas trouvé de critère différenciant ces deux figures.
On peut aussi explorer récursivement tous les votes possibles ayant la similarité minimum quand il y en a plusieurs (cela fait l'hypothèse que la solution optimale respecte ce critère même si elle n'est plus la seule, mais cela n'est même pas sûr), mais les calculs explosent compètement d'un point de vue combinatoire (cela est même plus mauvais que l'exhaustif). On pourrait sans doute trouver des bornes assez proches en testant au hasard quelques votes en haut de l'arbre d'exploration. Le code est ici.
- 1A. 1358. La ville d'Alice compte au plus 1358 habitants.
Soit E1 le nombre d'électeurs, chacun votant pour 10 candidats. Ainsi, le nombre total de voix est 10E1.
Comme il y a 25 candidats en tout, le nombre de voix du candidat C1 qui obtient le plus de suffrages est supérieur ou égal à 10E1 / 25. Au moins 40% des électeurs (arrondis à l'entier supérieur V1) sont donc satisfaits par son élection.
On recommence le raisonnement pour les électeurs qui n'ont pas voté pour C1 (ils sont au plus E2 = E1 – V1), et dont les voix se partagent entre 24 candidats. Le candidat C2 élu par eux obtient au moins V2 voix (V2 ≥ 10E2 / 24), ce qui satisfait en tout V1 + V2 votants.
On continue de proche en proche jusqu'à satisfaire tous les votants. Ce sera le cas au bout d'un nombre fini d'opérations. Mais il faut que ce le soit en 10 étapes au plus, puisque seuls 10 conseillers sont élus. On montre que c'est le cas quand E1 ≤ 1358, mais ce n'est plus sûr à partir de 1359 électeurs où une répartition des votes ne permet de satisfaire tous les votants qu'avec 11 élus. - 2B. 14. Le nombre de voix des électeurs de la ville de Bob doit être 14 pour satisfaire à la condition.
Dans la ville de Bob, on opère de la même façon en partant de E1 = 55 555 et en remplaçant 25 par 33. On voit que plus on augmente le nombre de voix de chaque électeur, plus le nombre d'étapes à la suite desquelles chacun sera satisfait (donc le nombre minimum d'élus) diminue. Ainsi, avec 13 votes, il faut attendre le quinzième élu pour satisfaire tout le monde.
Les deux nombres se rencontrent avec 14 votes (et 14 élus).