Shortlist 2010, C2¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Croatia
Concepts : Principe des tiroirs · Graphes : degrés, chemins, arbres · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 25 (page 26 du PDF)
Énoncé¶
On some planet, there are \(2^N\) countries (\(N \geq 4\)). Each country has a flag \(N\) units wide and one unit high composed of \(N\) fields of size \(1 \times 1\), each field being either yellow or blue. No two countries have the same flag.
We say that a set of \(N\) flags is diverse if these flags can be arranged into an \(N \times N\) square so that all \(N\) fields on its main diagonal will have the same color. Determine the smallest positive integer \(M\) such that among any \(M\) distinct flags, there exist \(N\) flags forming a diverse set.
Indices : les idées clés
- Exemple : les \(2^{N-2}\) drapeaux commençant par une case jaune puis une case bleue ne forment jamais une diagonale monochrome, donc \(M > 2^{N-2}\).
- Récurrence sur \(N\) à partir de \(N = 4\) : une colonne non monochrome contient, par les tiroirs, au moins \(2^{N-3} + 1\) cases d'une même couleur.
- Lemme de Hall (solution 2) : dans l'un des deux graphes bipartis colonnes–drapeaux (jaune ou bleu), il existe un couplage qui sature toutes les colonnes.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions).
Solution 1¶
Réponse : \(M = 2^{N-2} + 1\).
Quand on parle de la diagonale d'un carré, il s'agit toujours de la diagonale principale.
Soit \(M_N\) le plus petit entier strictement positif vérifiant la condition du problème. Montrons d'abord que \(M_N > 2^{N-2}\). Considérons l'ensemble des \(2^{N-2}\) drapeaux dont la première case est jaune et la deuxième bleue. Évidemment, les deux couleurs apparaissent sur la diagonale de tout carré \(N \times N\) formé par ces drapeaux.
Il reste à montrer que \(M_N \leq 2^{N-2} + 1\), ce qui donnera la réponse voulue. Commençons par établir cet énoncé pour \(N = 4\).
Supposons qu'on ait \(5\) drapeaux de longueur \(4\). Décomposons chaque drapeau en deux parties de \(2\) cases ; on note ainsi chaque drapeau \(LR\), où les drapeaux \(2 \times 1\) \(L, R \in \mathcal{S} = \{\mathrm{BB}, \mathrm{BJ}, \mathrm{JB}, \mathrm{JJ}\}\) sont ses parties gauche et droite. Faisons d'abord deux observations faciles sur les drapeaux \(2 \times 1\), qu'on vérifie à la main.
(i) Pour tout \(A \in \mathcal{S}\), il existe un seul drapeau \(2 \times 1\) \(C \in \mathcal{S}\) (éventuellement \(C = A\)) tel que \(A\) et \(C\) ne puissent pas former un carré \(2 \times 2\) à diagonale monochrome (pour \(\mathrm{BB}\), c'est \(\mathrm{JJ}\), et pour \(\mathrm{BJ}\), c'est \(\mathrm{JB}\)).
(ii) Soient \(A_1, A_2, A_3 \in \mathcal{S}\) trois éléments distincts ; alors deux d'entre eux peuvent former un carré \(2 \times 2\) à diagonale jaune, et deux d'entre eux peuvent former un carré \(2 \times 2\) à diagonale bleue (pour toutes les parties sauf \(\mathrm{BB}\), la paire \((\mathrm{BJ}, \mathrm{JB})\) convient aux deux affirmations, tandis que pour toutes les parties sauf \(\mathrm{BJ}\), ces paires sont \((\mathrm{JB}, \mathrm{JJ})\) et \((\mathrm{BB}, \mathrm{JB})\)).
Soient maintenant \(\ell\) et \(r\) les nombres de parties gauches et de parties droites distinctes de nos \(5\) drapeaux. Le nombre total de drapeaux est \(5 \leq r\ell\), donc l'un des facteurs (disons \(r\)) vaut au moins \(3\). D'autre part, \(\ell, r \leq 4\), donc il y a deux drapeaux ayant la même partie droite ; notons-les \(L_1R_1\) et \(L_2R_1\) (\(L_1 \neq L_2\)).
Ensuite, comme \(r \geq 3\), il existe des drapeaux \(L_3R_3\) et \(L_4R_4\) tels que \(R_1\), \(R_3\), \(R_4\) soient distincts. Soit \(L'R'\) le drapeau restant. D'après (i), l'une des paires \((L', L_1)\) et \((L', L_2)\) peut former un carré \(2 \times 2\) à diagonale monochrome ; on peut supposer que \(L'\), \(L_2\) forment un carré à diagonale bleue. Enfin, d'après (ii), les parties droites de deux des drapeaux \(L_1R_1\), \(L_3R_3\), \(L_4R_4\) peuvent aussi former un carré \(2 \times 2\) à diagonale bleue. En plaçant ces carrés \(2 \times 2\) sur la diagonale d'un carré \(4 \times 4\), on obtient la disposition voulue de quatre drapeaux.
Nous sommes prêts à prouver l'énoncé par récurrence sur \(N\) ; on vient de prouver le cas de base \(N = 4\). Pour l'hérédité, supposons \(N > 4\), considérons \(2^{N-2} + 1\) drapeaux de longueur \(N\) quelconques, et disposons-les en un grand drapeau de taille \((2^{N-2} + 1) \times N\). Ce drapeau contient une colonne non monochrome, puisque les drapeaux sont distincts ; on peut supposer que c'est la première. Par le principe des tiroirs, cette colonne contient au moins \(\left\lceil \frac{2^{N-2} + 1}{2} \right\rceil = 2^{N-3} + 1\) cases d'une même couleur (disons bleue). On appelle bons les drapeaux dont la première case est bleue.
Considérons tous les bons drapeaux et retirons-leur leur première case. On obtient au moins \(2^{N-3} + 1 \geq M_{N-1}\) drapeaux de longueur \(N - 1\) ; par hypothèse de récurrence, \(N - 1\) d'entre eux peuvent former un carré \(Q\) à diagonale monochrome. En remettant les cases retirées, on obtient un rectangle \((N - 1) \times N\), et il s'agit de le compléter en haut par un drapeau de plus.
Si \(Q\) a une diagonale jaune, on peut prendre n'importe quel drapeau dont la première case est jaune (il en existe un d'après le choix de la première colonne ; de plus, il n'est pas utilisé dans \(Q\)). Si au contraire la diagonale de \(Q\) est bleue, on peut prendre n'importe lequel des \(\geq 2^{N-3} + 1 - (N - 1) > 0\) bons drapeaux restants. Dans les deux cas, on obtient le carré \(N \times N\) voulu. \(\blacksquare\)
Solution 2¶
Voici une autre preuve de l'estimation \(M_N \leq 2^{N-2} + 1\). On n'utilise pas de récurrence, mais le lemme de Hall sur les couplages.
Considérons \(2^{N-2} + 1\) drapeaux distincts quelconques et disposons-les en un grand drapeau \((2^{N-2} + 1) \times N\). Construisons deux graphes bipartis \(G_\mathrm{j} = (V \cup V', E_\mathrm{j})\) et \(G_\mathrm{b} = (V \cup V', E_\mathrm{b})\) ayant le même ensemble de sommets, de la façon suivante. Soient \(V\) et \(V'\) l'ensemble des colonnes et l'ensemble des drapeaux considérés respectivement. L'arête \((c, f)\) est dans \(E_\mathrm{j}\) si l'intersection de la colonne \(c\) et du drapeau \(f\) est jaune, et \((c, f) \in E_\mathrm{b}\) sinon. Il faut alors prouver exactement que l'un des graphes \(G_\mathrm{j}\) et \(G_\mathrm{b}\) contient un couplage qui couvre tous les sommets de \(V\).
Supposons que ces couplages n'existent pas. D'après le lemme de Hall, il existe deux ensembles de colonnes \(S_\mathrm{j}, S_\mathrm{b} \subset V\) tels que \(\lvert E_\mathrm{j}(S_\mathrm{j}) \rvert \leq \lvert S_\mathrm{j} \rvert - 1\) et \(\lvert E_\mathrm{b}(S_\mathrm{b}) \rvert \leq \lvert S_\mathrm{b} \rvert - 1\) (dans les membres de gauche, \(E_\mathrm{j}(S_\mathrm{j})\) et \(E_\mathrm{b}(S_\mathrm{b})\) désignent respectivement les ensembles des sommets reliés à \(S_\mathrm{j}\) et à \(S_\mathrm{b}\) dans les graphes correspondants). Montrons que c'est impossible. Remarquons que \(S_\mathrm{j}, S_\mathrm{b} \neq V\) puisque \(N \leq 2^{N-2} + 1\).
Supposons d'abord \(S_\mathrm{j} \cap S_\mathrm{b} \neq \varnothing\) ; il existe donc un \(c \in S_\mathrm{j} \cap S_\mathrm{b}\). Chaque drapeau est relié à \(c\) dans \(G_\mathrm{j}\) ou dans \(G_\mathrm{b}\), donc \(E_\mathrm{j}(S_\mathrm{j}) \cup E_\mathrm{b}(S_\mathrm{b}) = V'\). Par conséquent, \(2^{N-2} + 1 = \lvert V' \rvert \leq \lvert E_\mathrm{j}(S_\mathrm{j}) \rvert + \lvert E_\mathrm{b}(S_\mathrm{b}) \rvert \leq \lvert S_\mathrm{j} \rvert + \lvert S_\mathrm{b} \rvert - 2 \leq 2N - 4\), ce qui est impossible pour \(N \geq 4\).
On a donc \(S_\mathrm{j} \cap S_\mathrm{b} = \varnothing\). Posons \(y = \lvert S_\mathrm{j} \rvert\), \(b = \lvert S_\mathrm{b} \rvert\). Par construction du graphe, tous les drapeaux de l'ensemble \(V'' = V' \setminus \big(E_\mathrm{j}(S_\mathrm{j}) \cup E_\mathrm{b}(S_\mathrm{b})\big)\) ont des cases bleues dans les colonnes de \(S_\mathrm{j}\) et des cases jaunes dans les colonnes de \(S_\mathrm{b}\). Les seules positions non déterminées de ces drapeaux sont donc les \(N - y - b\) restantes, d'où
ou, en posant \(c = y + b\), \(2^{N-c} + c > 2^{N-2} + 2\). C'est impossible puisque \(N \geq c \geq 2\). \(\blacksquare\)