Députés giflés

jacquot

Voici un exercice extrait d'une épreuve qualificative pour les Olympiades Françaises de Mathématiques.
Voir aussi la discussion Test d'entrée à l'Olympiade...
l'énoncé est assez cocasse.

Exercice 7 a écrit:

Chacun des 400 députés d’un parlement a giflé exactement un autre député.
Montrer qu’on peut créer une commission parlementaire de 134 députés telle qu’aucun membre de la commission n’ait giflé aucun autre membre.

Si je me limite aux permutations dans l'ensemble des 400 députés, je vois que le cas le plus défavorable est celui où presque toutes les orbites comptent trois éléments.
Mais il peut aussi arriver que certains députés aient reçu plusieurs gifles, je m'y perds encore...

Cette disjonction de cas est-elle nécessaire ou bien y a-t-il un raisonnement plus général?

gai requin

Peut-être le principe des tiroirs ?

jacquot

Merci gai requin,

Si tu vois une piste dans cette direction, ça m'intéressera.
La solution que j'entrevois serait plutôt un traitement avec des graphes
2n, on pourra envoyer à la commission un député sur deux (voir graphes a et e. En rouge, les députés écartés de la commission)
Si on s'est giflé en permutation circulaire dans un groupe d'effectif impair 2n+1, on pourra envoyer à la commission n députés sur les 2n+1 (voir graphes b et c)

Le graphe d présente une situation où certains députés ont recu plusieurs gifles. Il y aura autant d'extrémités libres que de confluences. Si j'exclus de la commission les deux députés qui se trouvent aux confluents, je me retrouve avec trois segments ouverts de députés. Là, je peux, sur chaque segment , envoyer à la Comission un député sur deux.

Bref, la situation la plus défavorable est celle où les 400 députés se sont giflés par triplettes (plus un carré, puisque 400= 132x3+4).
La Commission se compose alors de 132+2 députés.

Il reste à préciser un peu l'étude des graphes à confluences.
JLT a-t-il un corrigé de cette épreuve?
Quel traitement y est-il préconisé pour cet exercice?

JLT

N.B. Ce n'est pas un exercice pour une épreuve qualificative, c'est un exercice d'entraînement donné en cours d'année dans le cadre des "envois mensuels" (exercices corrigés par correspondance). Les épreuves qualificatives ont typiquement lieu

- vers Janvier pour la sélection pour le stage
- vers mars-avril pour la sélection aux olympiades Balkaniques, l'EGMO et les Balkaniques Junior
- vers mai pour les Olympiades Internationales.

jacquot

Bon, j'ai montré assez proprement que pour tout graphe de type "boucle", de 2n ou (2n+1) députés, on peut en sélectionner n pour la Commission.
Il faudrait maintenant montrer qu'il en va de même pour les graphes de type "arbre". Ça n'a pas l'air bien difficile.

@ suivre. jacquot

marco

Par récurrence, montrons que dans un ensemble de $n$ députés où chaque député donne au plus une gifle, on peut former une commission de au moins $n/3$ députés.
Soit un ensemble de $n$ députés.
Soit $n_2$ le nombre de députés qui reçoivent plus de $2$ gifles, $n_1$ le nombre de députés qui reçoivent exactement une gifle, $n_0$ le mombre de députés qui ne reçoivent aucune gifle.
$n_2=n-n_0-n_1$ où $n$ est le nombre de députés.
De plus $2 n_2+n_1\leq n$ car le nombre de gifles est inférieur ou égal au nombre de députés.
Si $n_0\geq n/3$ , on choisit les députés qui ne reçoivent aucune gifle comme commission parlementaire.
Sinon, $n_0 < n/3$, donc $n_2> n-n/3-n_1$ donc $n_2>2n/3-n_1$.
Donc $4n/3-2n_1+n_1<2n_2+n_1\leq n$. Donc
$n_1>n/3$. Donc il y a au moins $n/3$ députés qui ne reçoivent qu'une gifle. Non, cela ne marche pas....

jacquot

Bonsoir marco,

Ton idée de récurrence est intéressante.
Je n'avais pas vu le bug de ton raisonnement avant que tu ne te ravises. "Ça ne marche pas ..."
Qu'est-ce qui ne marche pas?
En tous cas, tes inégalités sont justes

Juste peut-être ceci
Tu supposes que la propriété est vraie jusqu'à un rang n-1 et tu veux prouver qu'alors elle reste vraie au rang n. Ce n'est pas tout à fait clair dans ton exposé.

Par ailleurs 134 est légèrement supérieur au tiers de 400.

Je pense à présent qu'une démonstration par récurrence est effectivement possible et que tu n'en es pas loin

marco

Cela ne marchait pas car le député qui ne recevait qu'une gifle, pouvait en donner une à un député de l'ensemble restant.
Je corrige.
Je suppose que la propriété est vraie jusqu'au rang $n-1$.

Soit $A$ l'ensemble des députés qui ne reçoit pas de gifle, $B$ l'ensemble des députés giflés par au moins un des députés de $A$. $C$ l'ensemble des députés restant. Aucun député de $A$ ne gifle un député de $C$. Aucun député de $C$ ne gifle un député de $A$.
De plus $|B| \leq |A|$.
Et $|A|+ |B| +|C|=n$.

Si $|A|=0$, $n_0=0$ et le graphe est constitué de boucles d'aprés l'inégalité $2n_2+n_1\leq n_0+n_1+n_2$ (car alors $2n_2 \leq n_2$, donc $n_2=0$). Et on conclut, d'après ce que tu as montré sur les boucles.
Si $|A|>0$, on peut trouver par hypothèse de récurrence une commission $D$ pour l'ensemble $C$, constitué d'au moins $|C|/3$ députés. En effet, on supprime les gifles données par un député de $C$ à un député de $B$, et celles données par un député de $B$ à un député de $C$. On rajoute l'ensemble $A$ à cette commission $D$, cela nous donne une commission pour l'ensemble complet, car aucun député de $A$ ne gifle un député de $C$, et aucun député de $C$ ne gifle un député de $A$.
Reste à voir que $|A|+\frac{1}{3}|C| \geq \frac{1}{3}(|A| +|B|+|C|)$, c'est-à-dire
$\frac{2}{3}|A| \geq \frac{1}{3}|B|$ ,ce qui est vrai (car $|A| \geq |B|$).

jacquot

(tu) marco,

Ton approche est vraiment intéressante et complète bien l'étude que j'avais fait plus haut pour les boucles.

Je pensais m'en sortir descriptive, mais c'était un peu difficile à rédiger.
Pour les structures de type "arbre", il y a autant d'extrémités libres que de confluences et sur chaque rameau ayant une extrémité lirbre, on pouvait retenir au moins un député sur deux .Donc de chaque "arbre, on pouvait envoyer en commission au moins le tiers des députés.
Ensuite il fallait encore s'intéresser aux structures mixtes du genre figure d. Elles sont découpables.
Mais pour rédiger tout ça proprement, c'était galère et ça nécessitait des croquis.
J'aime bien ta façon de terminer.
Merci pour l'intérêt porté à cet exercice.

Amicalement. jacquot

Judoboy

Ca me paraît démesurément difficile pour des lycéens non ?

Judoboy

On prend le premier député ; il a reçu une gifle et en a donné une. On demande à l'assemblée "qui n'a ni giflé cette persone, ni reçu de gifle de sa part ?" Il reste 400 candidats, moins le député 1, moins au pire les 2 qui ont reçu/donné une gifle.

Le député 2 se présente. A eux 2 ils ont distribué 2 gifles et reçu 2 ; on pose la même question, il reste encore au moins 394 candidats. Un troisième se pointe, même question, il reste encore au moins 400-3(les 3 déjà présentés)-3*2 candidats (les éventuelsgiflés/gifleurs).

On réitère et arrivé au 133ème il reste au moins encore 400-133-(2*133) candidats, i.e. il nous reste le 134 ème.




Et voilà

Je me demande si les maths ça pourrit pas un peu le cerveau, j'ai dessiné des graphes et imaginé des matrices 400*400 pendant 3/4 d'heure avant de trouver ça...

marco

Un député peut avoir reçu deux gifles ou plus.

Judoboy

Zut. Je me disais aussi c'est trop beau. Ca doit pouvoir s'arranger.

P.S. : Marco , tu n'initialises pas ta récurrence, or la propriété est fausse pour n=2, j'arrive pas à voir si ça pose problème ?

marco

Non, elle n'est pas fausse pour $n=2$. Si on choisit un des deux députés, il ne se gifle pas lui-même. Et on a bien $1 \geq \frac{2}{3}$.
(La commission est constitué d'un seul député)

Judoboy

Ah bah oui bien sûr.
Bon sinon le fait que des députés se fassent muti-giffler ne pose pas de problème. Si n0 députés ont reçu 2 gifles ou plus, n0 députés n'en n'ont pas pris. On les met tous ensemble, ça fait un début de commission. Il reste au moins 400-n0(ceux qu'on a déjà pris)-n0(ceux qui ont pris 2 baffes ou plus)-n0(ceux qui ont été giflés par la commission initiale) candidats parmi ceux qui n'ont pris qu'une seule baffe, donc 400-3*n0.

A chaque fois qu'on sélectionne un candidat ayant pris une seule baffe on retire au plus 3 candidats potentiels parmi ceux restants, i.e. si on rajoute n1 candidats ayant pris une baffe il en restera 400-3*n0-3*n1 et ça s'arrête quand on n'a plus de candidats, i.e. 3*n0+3*n1>400, i.e. n0+n1>133 soit au 134ème député au pire.

Et j'ai même pas sélectionné parmi ceux ayant pris plusieurs baffes donc y a de la marge, je sais pas si 134 c'est la meilleure valeur qu'on puisse trouver.

Siméon

Oui, 134 est optimal. Prendre 132 triangles et 1 carré (je crois que jacquot l'avait déjà donné d'ailleurs). Sinon j'ai une jolie solution que je posterai plus tard

jacquot

Excellent, ton raisonnement, Judoboy.
Ça paraît carrément simple, et les graphes n'étaient pas indispensables.

Amicalement. jacquot

Siméon

Bon je me lance dans une longue explication écrite, mais il suffirait en fait d'un bon dessin pour comprendre.

On va considérer le graphe non orienté dont les sommets sont les députés et tels qu'une arête existe entre $x$ et $y$ si et seulement si $x$ a giflé $y$ ou $y$ a giflé $x$. Clairement on ne perd rien à travailler composante connexe par composante quitte à réunir des sous-commissions (il n'y aura aucune interaction entre elles). Soit donc $C$ une telle composante formée de $n$ députés. On va montrer qu'on peut trouver une sous-commission dans $C$ composée d'au moins $\frac{n}{2}-1$ députés.

L'essentiel de la preuve est dans la remarque suivante : $C$ contient une unique boucle. Pour le voir, le plus simple est peut-être de redessiner $C$ en ajoutant les députés au fur et à mesure :
1 -- On prend un premier député de $C$ quelconque puis on ajoute ses descendants en suivant la lignée de gifles distribuées. On finit par boucler (car $C$ est fini).
2 -- On prend un député de $C$ qui n'a pas encore été ajouté et on suit sa lignée. Par connexité, on finit par rejoindre la lignée déjà dessinée, et dès que ce moment arrive on n'en sort plus.
3 -- On répète l'étape 2 tant qu'il reste des députés de $C$ non ajoutés.

Ceci fait, on retire virtuellement une arête quelconque de la boucle, ce qui fait de $C$ un arbre. Partant d'un sommet quelconque, on note alors $A$ l'ensemble des sommets atteignables en un nombre pair d'étapes, $B$ l'ensemble des sommets atteignables en un nombre impair d'étapes. Alors $A \cup B = C$ donc quitte à échanger $A$ et $B$ on peut supposer que $|A| \geq n/2$. Alors $A$ forme une sous-commission\footnote{La distance de graphe entre deux députés de $A$ est un nombre pair.} sauf dans le cas où on a été amené à prendre les deux extrémités de l'arête retirée, auquel cas on enlève un des deux.

Il reste à voir que $\frac{n}{2}-1 > \frac{n}{3}$ si $n > 3$ et que $n=3$ fournit $1 = \frac{n}{3}$ député. Comme $400$ n'est pas divisible par $3$, l'ensemble des sous-commissions forme une commission ayant strictement plus de $400/3$ membres, donc au moins $134$.

jacquot

Oui, Siméon,

C'est un peu la solution descriptive que je cherchais plus haut, mais je trouve que le raisonnement de Judoboy est plus puissant, Puisqu'il ne s'occupe pratiquement pas de la structure des interconnexions.

Amicalement. jacquot

Siméon

@jaquot : je suis tout à fait d'accord à toi. Je cherchais une preuve reprenant tes idées qui donnent une compréhension bien plus complète de la structure du graphe. Et puis je trouvais ça visuellement très joli l'arbre à une boucle

pdepasse

Bonjour à tous,

un truc m'échappe dans ce qu'écrit Judoboy (je marque en gras souligné ce qui n'est pas clair (pour moi!)):

A chaque fois qu'on sélectionne un candidat ayant pris une seule baffe on retire au plus 3 candidats potentiels parmi ceux restants, i.e. si on rajoute n1 candidats ayant pris une baffe il en restera 400-3*n0-3*n1 et ça s'arrête quand on n'a plus de candidats, i.e. 3*n0+3*n1>400, i.e. n0+n1>133 soit au 134ème député au pire.

Si le une signifie une seule, pourquoi 3*n0+3*n1 dépasserait-il nécessairement 400?

Si le une signifie au moins une ,pourquoi retirerait-on au plus 3 candidats potentiels parmi ceux restants lorsqu'on vient d'en sélectionner un?

Bien des chances que ce soit moi et non l'énoncé qui ne soit pas très clair!

Cordialement
Paul

Judoboy

Une signifie une seule, on n'atteint pas forcément 400 en fait, c'est ma remarque à la fin, on va la plupart du temps se retrouver avec une commission de plus de 134 députés, ça dépendra des cas. Mais on est sûr d'en avoir strictement plus de 133.

jacquot

Prenons le cas de 6 députés qui se sont giflés en boucle (voir figure a)

pdepasse

Je cherchais midi à quatorze heures!
Merci à tous les deux
Paul