Shortlist 2017, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Russia
Concepts : Double comptage · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 46 (page 48 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(n > 1\) be an integer. An \(n \times n \times n\) cube is composed of \(n^3\) unit cubes. Each unit cube is painted with one color. For each \(n \times n \times 1\) box consisting of \(n^2\) unit cubes (of any of the three possible orientations), we consider the set of the colors present in that box (each color is listed only once). This way, we get \(3n\) sets of colors, split into three groups according to the orientation. It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of \(n\), the maximal possible number of colors that are present.
Indices : les idées clés
- Classer les couleurs selon leur nombre d'apparitions (solution 1) : une, deux, ou au moins trois fois ; on note \(n_1, n_2, n_3\) le nombre de cubes correspondants.
- Double comptage (solution 1) : une inégalité locale \(4|X \cap M_1| + |X \cap M_2| \leq 3n+1\), sommée sur toutes les boîtes d'une orientation, donne \(4n_1 + n_2 \leq n(3n+1)\).
- Récurrence (solution 2) : on généralise avec des cubes « invisibles », on efface un ensemble de couleurs commun à trois boîtes et on passe au cube \((n-1)^3\).
- Construction symétrique : couleurs formées d'orbites de la permutation circulaire des coordonnées.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions).
Réponse : le nombre maximal de couleurs est \(\dfrac{n(n+1)(2n+1)}{6}\).
Solution 1¶
Appelons une boîte \(n \times n \times 1\) une \(x\)-boîte, une \(y\)-boîte ou une \(z\)-boîte selon la direction de son petit côté. Soit \(C\) le nombre de couleurs d'une configuration valide. Commençons par la majoration de \(C\).
Soient \(\mathcal{C}_1\), \(\mathcal{C}_2\), \(\mathcal{C}_3\) les ensembles des couleurs qui apparaissent dans le grand cube exactement une fois, exactement deux fois, et au moins trois fois, respectivement. Soit \(M_i\) l'ensemble des petits cubes dont la couleur est dans \(\mathcal{C}_i\), et \(n_i = |M_i|\).
Soit \(X\) une \(x\)-boîte, et soient \(Y\) et \(Z\) une \(y\)-boîte et une \(z\)-boîte ayant le même ensemble de couleurs que \(X\).
Affirmation. \(4|X \cap M_1| + |X \cap M_2| \leq 3n + 1\).
Preuve. Deux cas.
Cas 1 : \(X \cap M_1 \neq \varnothing\). Un cube de \(X \cap M_1\) a une couleur unique qui doit apparaître dans les trois boîtes \(X\), \(Y\), \(Z\) ; il est donc dans \(X \cap Y \cap Z\), qui est un seul petit cube. Ainsi \(X \cap M_1 = X \cap Y \cap Z\) et \(|X \cap M_1| = 1\).
Considérons maintenant les cubes de \(X \cap M_2\). Au plus \(2(n-1)\) d'entre eux sont dans \(X \cap Y\) ou \(X \cap Z\) (car le cube de \(X \cap Y \cap Z\) est dans \(M_1\)). Soit \(a\) un autre cube de \(X \cap M_2\). Il existe exactement un autre cube \(a'\) de la même couleur que \(a\). Mais \(Y\) et \(Z\) doivent tous deux contenir un cube de cette couleur, et \(a \notin Y \cup Z\), donc \(a' \in Y \cap Z\) (et \(a' \notin X \cap Y \cap Z\)). L'application \(a \mapsto a'\) est clairement injective, donc le nombre de tels cubes \(a\) est au plus \(|(Y \cap Z) \setminus X| = n - 1\). Ainsi \(|X \cap M_2| \leq 2(n-1) + (n-1) = 3(n-1)\) et
Cas 2 : \(X \cap M_1 = \varnothing\). Le même argument s'applique avec quelques changements : \(X \cap M_2\) contient au plus \(2n - 1\) cubes de \(X \cap Y\) ou \(X \cap Z\), et tout autre cube \(a\) de \(X \cap M_2\) correspond à un \(a' \in Y \cap Z\) (éventuellement avec \(a' \in X\)) ; il y en a donc au plus \(n\). D'où \(|X \cap M_2| \leq (2n - 1) + n = 3n - 1\), ce qui est même mieux que nécessaire. \(\square\)
En sommant l'affirmation sur toutes les \(x\)-boîtes \(X\) (qui partitionnent le grand cube), on obtient
Évidemment, on a aussi \(n_1 + n_2 + n_3 = n^3\).
Estimons maintenant \(C\). Par définition des \(M_i\), on a \(n_i \geq i\,|\mathcal{C}_i|\), donc
Il reste à donner un coloriage convenable avec ce nombre de couleurs. Repérons les petits cubes par leurs coordonnées \((i, j, k) \in \{1, \ldots, n\}^3\). Pour chaque couleur, on donne l'ensemble des cubes de cette couleur :
- \(n\) singletons \(S_i = \{(i,i,i)\}\) (pour \(1 \leq i \leq n\)) ;
- \(3\binom{n}{2}\) paires \(D^1_{i,j} = \{(i,j,j), (j,i,i)\}\), \(D^2_{i,j} = \{(j,i,j), (i,j,i)\}\) et \(D^3_{i,j} = \{(j,j,i), (i,i,j)\}\) (pour \(1 \leq i < j \leq n\)) ;
- \(2\binom{n}{3}\) triplets \(T_{i,j,k} = \{(i,j,k), (j,k,i), (k,i,j)\}\) (pour \(1 \leq i < j < k \leq n\) ou \(1 \leq i < k < j \leq n\)).
On vérifie facilement que les \(i\)-ièmes boîtes des trois orientations contiennent le même ensemble de couleurs, et que le nombre de couleurs utilisées est
Solution 2¶
Considérons une nouvelle version du problème : chaque petit cube peut avoir une couleur, ou être invisible (pas les deux). On forme les ensembles de couleurs des boîtes \(n \times n \times 1\) comme avant (« invisible » n'est pas une couleur), groupés par orientation. On exige seulement que tout ensemble non vide d'un groupe apparaisse aussi dans les deux autres groupes. Quel est alors le nombre maximal de couleurs ?
Appelons étrange un grand cube \(n \times n \times n\) dont le coloriage satisfait ces nouvelles conditions, et soit \(D\) son nombre de couleurs. Tout cube satisfaisant les conditions de départ est étrange, donc \(\max(D)\) majore la réponse cherchée.
Affirmation. \(D \leq \dfrac{n(n+1)(2n+1)}{6}\).
Preuve. Récurrence sur \(n\). Pour \(n = 1\), le cube a au plus une couleur.
Soit \(A\) un cube étrange \(n \times n \times n\), \(n \geq 2\). Si \(A\) est entièrement invisible, \(D = 0\) et c'est fini. Sinon, choisissons un ensemble de couleurs non vide \(\mathcal{S}\), qui correspond à trois boîtes \(X\), \(Y\), \(Z\) d'orientations différentes.
Rendons invisibles tous les cubes de \(A\) dont la couleur est dans \(\mathcal{S}\). Les boîtes \(X\), \(Y\), \(Z\) deviennent entièrement invisibles ; on peut les jeter et se concentrer sur le cube restant \(B\), de taille \((n-1) \times (n-1) \times (n-1)\). Les ensembles de couleurs de toutes les boîtes de \(B\) sont ceux de \(A\) privés exactement des couleurs de \(\mathcal{S}\), et de rien d'autre ! Donc tout ensemble non vide apparaissant dans un groupe de \(B\) apparaît encore dans toutes les orientations (il se peut qu'un ensemble vide de \(B\) n'ait correspondu qu'à \(X\), \(Y\) ou \(Z\) avant qu'on les jette, mais on n'exige pas que les ensembles vides se correspondent). Bref, \(B\) est étrange.
Par hypothèse de récurrence, \(B\) a au plus \(\frac{(n-1)n(2n-1)}{6}\) couleurs. Comme \(\mathcal{S}\) contient au plus \(n^2\) couleurs (celles d'une boîte), \(A\) a au plus
couleurs. \(\square\)
Enfin, la construction de la solution précédente fournit un coloriage (sans cube invisible) qui atteint ce maximum. \(\blacksquare\)