Dans une élection, deux candidats s’affrontent. Supposons qu’il y ait $G$ groupes d’électeurs, chacun contenant $V$ électeurs (avec $G$ ≥ 2 et $V$ ≥ 3). Si un candidat dispose d’informations très précises issues des sondages et peut pratiquer le gerrymandering, quel est le nombre minimal d’électeurs favorables dont il a besoin pour gagner l’élection ? Et quel est approximativement le pourcentage de voix favorables nécessaires, si G et V deviennent très grands ?
Soit
g le plus petit entier strictement supérieur à G/2
v le plus petit entier strictement supérieur à V/2
Alors, on va prouver que le nombre minimal de votes favorables nécessaires est
$$gv,$$
sauf si $G$ et $V$ sont tous deux pairs, dans ce cas, le nombre minimal de voix favorables nécessaires est $$gv - 1.$$
Alors dans les deux cas, le pourcentage de voix favorables nécessaires est supérieur à 25 %, car
dans le premier cas : $$gv>(G/2)(V/2)$$
et dans le deuxième cas : $$gv−1=(G/2+1)(V/2+1)−1>(G/2)(V/2)$$
Quand $G$ et $V$ deviennent très grands, $g$ devient approximativement $G/2$ et $v$ devient approximativement $V/2$, donc $gv – 1$ devient approximativement $gv$ : on en déduit donc que le pourcentage requis est proche de 25 %.
Supposons que V est impair. Dans ce cas, il n’est pas possible d’avoir une égalité dans un groupe.
Alors, g est le nombre minimal de groupes à gagner pour remporter l’élection et v est le nombre minimal de voix favorables par groupe. Donc, le nombre total minimal de voix favorables est donc $gv$.
Supposons que V est pair. Ici, une égalité dans un groupe est possible : Pour gagner un groupe, un candidat a donc besoin de $V/2 + 1$ voix favorables et pour avoir une égalité dans un groupe, $V/2$ voix suffisent. Supposons que le candidat A gagne dans $w$ groupes et fasse égalité dans $t$ groupes. Alors, B fait égalité dans ces mêmes $t$ groupes, et gagne dans $G - w - t$ groupes. Le candidat A gagne alors l’élection si $w > G - w - t$, c-à-d si la condition suivante est vérifiée :
$$2w+t>G$$
Soit G impair : On peut donc supposer (en diminuant t de 1 si nécessaire) que t est pair. Si t = 0, on retombe sur le cas précédent, le candidat nécessite exactement $gv$ voix pour gagner l’élection. Si $t ≥ 2$, on peut réduire $t$ de 2 et augmenter $w$ de 1, ce qui permet d’économiser des voix , donc on peut écarter ce cas.
Soit G pair : Alors $t = 0$ ou (en diminuant $t$ de 1), on peut supposer que $t$ est impair. Si $t = 1$, on a besoin d’une voix de moins qu’avec $t = 0$, donc $gv - 1$ voix suffisent. Si $t$ est impair et supérieur à 1, alors on peut encore réduire $t$ de 2 et augmenter $w$ de 1, ce qui permet au candidat d’économiser plus de voix et donc ce cas aussi peut être écarté.
Dans une élection avec $N$ électeurs (où $N$ ≥ 3), deux candidats s’opposent. Supposons que l’un des deux puisse faire du gerrymandering de manière extrême, c’est-à-dire choisir le nombre de groupes, le nombre d’électeurs dans chaque groupe, et la composition des groupes. Combien de voix favorables lui faut-il pour gagner dans ce cas de gerrymandering extrême ?
Une seule voix favorable ne suffit pas, car elle ne permet de gagner qu’un seul groupe au maximum. Et s’il n’y a qu’un seul groupe, il n’aura pas la majorité dans ce groupe.
Deux voix favorables suffisent (quelle que soit la taille de $N$). Le candidat peut créer trois groupes : deux groupes contenants chacun un électeur favorable et un troisième groupe contenant tous les autres électeurs. Finalement, le candidat gagne 2 groupes sur 3, et donc remporte l’élection.