[Proposed, niv 2] élections .... non truquées


  • Math&Maroc

    Dans une élection au royaume des bisounours, NN électeurs doivent choisir kk représentants. Chaque électeur doit indiquer exactement mm choix distincts, où mkm \leq k <N N. Chaque électeur est aussi un candidat et chaque candidat a un âge différent. Les candidats sont classés selon le nombre de votes qu'ils ont reçus et les k k candidats qui ont reçu le plus grand nombre de votes sont élus. Dans le cas d'égalité, le candidat le plus âgé est élu.
    Quel est le nombre minimal de votes qu'un candidat doit recevoir pour s'assurer d'être élu ?



  • On note les bisounours a1,a2,a3.....,ana_1,a_2,a_3.....,a_n tel qu ils sont classés en fonction de leur age.
    CasCas 1 Si mnk[k+1]mn \doteq k [k+1] ou bien mn=a(k+1)+kmn=a(k+1)+k
    Alors chaque habitant a besoin de a+1a+1 voix.
    Supposons que un habitant avec a+1a+1 voix n est pas élu .
    Alors (k+1)(a+1)mn(k+1)(a+1) \leq mn ou encore (k+1)(a+1)a(k+1)+k(k+1)(a+1)\leq a(k+1)+k
    Equivalent à (k+1)k (k+1) \leq k Ce qui est absurde.
    Pour montrer qu un habitant avec aa voix peut ne pas etre élu il suffit d'oberver que mn=a+k(a+1)mn=a+k(a+1)
    CasCas 2 mnmn n est pas congru à k[k+1]k[k+1] Alors mn=a(k+1)+b mn=a(k+1)+b avec bb<kk
    On va montrer que les habitants a1,a2,a3,...akba_1,a_2,a_3,...a_{k-b} ont besoins de aa voix pour etre élus.
    En effet supposons le contraire
    Alors mn(kb)a+(a+1)(b+1)mn\geq (k-b)a+(a+1)(b+1)
    ak+a+bkaab+ab+a+b+1ak+a+b\geq ka -ab +ab +a +b +1
    010 \geq 1 Absurde !
    Montrons maintenant que aa est bien minimal pour cette catégorie.
    Il suffit de prouver que mn(kb)(a1)+(a+1)(b+1)mn \geq (k-b)(a-1)+(a+1)(b+1)
    Ou encore kb+1 k \geq b+1 ce qui est vrai.
    Montrons maintenant que pour le reste des habitants akb+1.....,ana_{k-b+1}....., a_n
    Ils ont besoin de a+1a+1 voix pour etre élus.
    Supposons le contraire
    Alors mn(k+1)(a+1)mn \geq (k+1)(a+1) ou encore bk+1b\geq k+1 ce qui est absurde.
    Montrons que maintenant un habitant parmi le deuxieme groupe peut ne pas etre élu avec aa voix.
    Il suffit que les membres plus agés que lui aient aa voix et il y en a au moins kb1 k-b-1
    Et que il y ait b+1b+1 autres habitants avec a+1a+1 voix.
    Donc on a besoin de a(kb1)+(a+1)(b+1)a(k-b-1)+(a+1)(b+1) voix =ak+b+1mn=ak+b+1 \leq mn
    Ce qui clot la preuve.
    Sauf erreur


Log in to reply
 

Looks like your connection to Expii Forum was lost, please wait while we try to reconnect.