Un problème de grands-pères et le principe des tiroirs

Proof.

À chaque grand-père on associe un sommet, et à chaque enfant une arête joignant ses deux grands-pères. On obtient ainsi une famille

$$> \mathcal F=\{e_1,\ldots,e_{20}\} >$$

de $20$ arêtes telle que

$$> e_i\cap e_j\neq\varnothing > \qquad (i\neq j). >$$

Autrement dit, les arêtes sont deux à deux intersectantes.

Nous allons lire cette configuration dans l'esprit du pelage orienté : soit la famille se réduit autour d'un même sommet, soit le processus fait apparaître un petit coeur opaque.

Choisissons une arête

$$> e_1=\{A,B\}. >$$

Puisque toute autre arête doit rencontrer $e_1$, toute arête contient $A$ ou $B$.

Premier cas : étoile.

Supposons que toutes les arêtes contiennent $A$. Alors $A$ est grand-père des $20$ enfants et, en particulier,

$$> 20\geq 14. >$$

La conclusion est donc immédiate.

Deuxième cas : apparition d'un coeur opaque.

Supposons qu'il existe une arête ne contenant pas $A$. Comme elle doit rencontrer $\{A,B\}$, elle est nécessairement de la forme

$$> e_2=\{B,C\}, > \qquad C\neq A. >$$

Si maintenant toutes les arêtes contiennent $B$, alors $B$ est grand-père des $20$ enfants et nous avons encore terminé.

Sinon, il existe une arête qui ne contient pas $B$. Cette arête doit rencontrer à la fois

$$> \{A,B\} > \qquad\text{et}\qquad > \{B,C\}. >$$

Comme elle ne contient pas $B$, elle est nécessairement

$$> e_3=\{A,C\}. >$$

Nous avons donc fait apparaître le triangle

$$> \{A,B\},\qquad > \{B,C\},\qquad > \{C,A\}. >$$

[ scale=1.2, vertex/.style={circle,draw,minimum size=9mm,inner sep=0pt} ] node[vertex] (A) at (90:2) {$A$}; node[vertex] (B) at (210:2) {$B$}; node[vertex] (C) at (330:2) {$C$};

draw[thick] (A)--(B); draw[thick] (B)--(C); draw[thick] (C)--(A);

Ce triangle joue ici le rôle du coeur opaque : une arête quelconque doit rencontrer chacune de ses trois arêtes.

Soit en effet

$$> e=\{x,y\}\in\mathcal F. >$$

On doit avoir simultanément

$$> e\cap\{A,B\}\neq\varnothing, >$$

$$> e\cap\{B,C\}\neq\varnothing, >$$

et

$$> e\cap\{C,A\}\neq\varnothing. >$$

Comme $e$ ne possède que deux extrémités, cela impose

$$> e\subseteq\{A,B,C\}. >$$

Par conséquent,

$$> \boxed{ > \mathcal F > \subseteq > \bigl\{ > \{A,B\},\{B,C\},\{C,A\} > \bigr\}. > } >$$

Ainsi, après le pelage de toutes les possibilités extérieures, la configuration entière est concentrée sur le coeur

$$> C=\{A,B,C\}. >$$

Notons

$$> d(A),\qquad d(B),\qquad d(C) >$$

le nombre de petits-enfants respectifs de $A,B,C$.

Chaque enfant contribue exactement $2$ aux degrés, puisqu'il possède deux grands-pères. Par conséquent,

$$> d(A)+d(B)+d(C) > = > 2|\mathcal F| > = > 2\times20 > = > 40. >$$

Il s'agit maintenant d'un argument de couche finale : les $40$ incidences sont supportées par seulement trois sommets. Ainsi,

$$> \max\{d(A),d(B),d(C)\} > \geq > \left\lceil\frac{40}{3}\right\rceil. >$$

Or

$$> \left\lceil\frac{40}{3}\right\rceil > = > 14. >$$

Donc

$$> \boxed{ > \max\{d(A),d(B),d(C)\}\geq 14. > } >$$

L'un des grands-pères possède donc au moins $14$ petits-enfants dans cette maternelle.

∎