Shortlist 2011, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : non indiqué
Concepts : Double comptage · Coloriages et pavages · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 39 (page 40 du PDF)
Figures reprises du livret officiel de la Shortlist.
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
On a square table of \(2011\) by \(2011\) cells we place a finite number of napkins that each cover a square of \(52\) by \(52\) cells. In each cell we write the number of napkins covering it, and we record the maximal number \(k\) of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value of \(k\)?
Indices : les idées clés
- Résidus modulo \(52\) : avec \(2011 = 52m - 17\) (\(m = 39\)), sur chaque ligne les sommes \(s_i\) des cases d'indice \(\equiv i \pmod{52}\) sont toutes égales au nombre de serviettes qui coupent la ligne ; \(s_1, \ldots, s_{35}\) ont \(m\) termes et \(s_{36}, \ldots, s_{52}\) en ont \(m - 1\).
- Lignes riches et pauvres : une ligne riche a au moins \(17\) « mauvaises » cases, une ligne pauvre au moins \(35\) ; on place des « fraises » sur ces cases.
- Double comptage des fraises : au plus \(2g\), et au moins \(2(35m \cdot 34 + 17(m - 1) \cdot 17)\), d'où \(g \geq 57392\) ; une construction par blocs de serviettes atteint cette borne.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions et trois remarques).
Réponse : \(2011^2 - \big((52^2 - 35^2) \cdot 39 - 17^2\big) = 4044121 - 57392 = 3986729\).
Solution 1¶
Posons \(m = 39\) ; alors \(2011 = 52m - 17\). Commençons par un exemple où \(3986729\) cases portent le même nombre strictement positif.
Numérotons les colonnes de gauche à droite et les lignes de bas en haut par \(1, 2, \ldots, 2011\). On désigne chaque serviette par les coordonnées de sa case inférieure gauche. Il y a quatre sortes de serviettes : d'abord, toutes les serviettes \((52i + 36, 52j + 1)\) avec \(0 \leq j \leq i \leq m - 2\) ; ensuite, toutes les serviettes \((52i + 1, 52j + 36)\) avec \(0 \leq i \leq j \leq m - 2\) ; puis toutes les serviettes \((52i + 36, 52i + 36)\) avec \(0 \leq i \leq m - 2\) ; et enfin la serviette \((1, 1)\). Les différents groupes de serviettes sont représentés par différentes hachures sur la figure.
Hormis les cases qui portent deux hachures différentes ou plus, toutes les cases contiennent le nombre \(1\). On calcule facilement que le nombre de ces cases exceptionnelles est \((52^2 - 35^2)m - 17^2 = 57392\).
Il reste à prouver que \(3986729\) est un majorant du nombre de cases contenant le même nombre. Considérons une configuration de serviettes et un entier \(M > 0\). Supposons qu'il y ait \(g\) cases contenant un nombre différent de \(M\). Il suffit de montrer que \(g \geq 57392\). Dans toute la solution, une ligne désigne une rangée ou une colonne.
Considérons une ligne \(\ell\). Soient \(a_1, \ldots, a_{52m-17}\) les nombres écrits dans ses cases consécutives. Pour \(i = 1, 2, \ldots, 52\), posons \(s_i = \sum_{t \equiv i \pmod{52}} a_t\). Les sommes \(s_1, \ldots, s_{35}\) ont \(m\) termes chacune, tandis que \(s_{36}, \ldots, s_{52}\) en ont \(m - 1\). Chaque serviette qui coupe \(\ell\) contribue exactement pour \(1\) à chaque \(s_i\) ; donc le nombre \(s\) de ces serviettes vérifie \(s_1 = \cdots = s_{52} = s\). On dit que la ligne \(\ell\) est riche si \(s > (m - 1)M\), et pauvre sinon.
Supposons \(\ell\) riche. Dans chacune des sommes \(s_{36}, \ldots, s_{52}\), il y a alors un terme supérieur à \(M\) ; considérons tous ces termes, et appelons les cases correspondantes les mauvaises cases riches de cette ligne. Chaque ligne riche contient donc au moins \(17\) cases mauvaises pour elle.
Si au contraire \(\ell\) est pauvre, alors certainement \(s < mM\), donc dans chacune des sommes \(s_1, \ldots, s_{35}\) il y a un terme inférieur à \(M\) ; on appelle les cases correspondantes les mauvaises cases pauvres de cette ligne. Chaque ligne pauvre contient donc au moins \(35\) cases mauvaises pour elle.
Appelons petits les indices congrus à \(1, 2, \ldots, 35\) modulo \(52\), et grands les autres (congrus à \(36, 37, \ldots, 52\)). Une ligne est grande ou petite selon son indice. Par définition, toutes les mauvaises cases riches des rangées sont dans les grandes colonnes, tandis que les pauvres sont dans les petites colonnes, et inversement.
Sur chaque ligne, posons une fraise sur chaque case mauvaise pour cette ligne. De plus, pour chaque petite ligne riche, posons une fraise supplémentaire sur chacune de ses mauvaises cases (riches). Une case reçoit les fraises de sa rangée et de sa colonne indépendamment.
Une case portant une fraise contient un nombre différent de \(M\). Si cette case reçoit une fraise par la règle supplémentaire, elle contient un nombre supérieur à \(M\) ; de plus, elle est dans une petite rangée et une grande colonne, ou inversement. Supposons qu'elle soit dans une petite rangée ; alors elle n'est pas mauvaise pour sa colonne, et elle a donc au plus deux fraises. D'autre part, si la règle supplémentaire ne s'applique pas à une case, elle a aussi au plus deux fraises. Le nombre total \(N\) de fraises est donc au plus \(2g\).
Estimons \(N\) d'une autre façon. Pour chacune des \(2 \cdot 35m\) petites lignes, on a posé au moins \(34\) fraises si elle est riche et au moins \(35\) si elle est pauvre, donc au moins \(34\) dans tous les cas. De même, pour chacune des \(2 \cdot 17(m - 1)\) grandes lignes, on a posé au moins \(\min(17, 35) = 17\) fraises. En sommant sur toutes les lignes, on obtient
comme voulu. \(\blacksquare\)
Remarque 1. Le même raisonnement s'applique si l'on remplace \(52\) par \(R\) et \(2011\) par \(Rm - H\), où \(m\), \(R\) et \(H\) sont des entiers avec \(m, R \geq 1\) et \(0 \leq H \leq \frac{1}{3}R\). Des informations plus précises sont données après la solution suivante.
Solution 2¶
On présente une autre preuve de la majoration, qui est la partie difficile du problème. Posons \(S = 35\), \(H = 17\), \(m = 39\) ; la taille de la table est \(2011 = Sm + H(m - 1)\) et celle des serviettes est \(52 = S + H\). Fixons un entier \(M > 0\) et disons qu'une case est vicieuse si elle contient un nombre différent de \(M\). Montrons qu'il y a au moins \(H^2(m - 1) + 2SHm\) cases vicieuses.
Introduisons d'abord un vocabulaire. Comme dans la solution précédente, on numérote rangées et colonnes et l'on utilise les notions d'indices et de lignes petits et grands : un indice est petit s'il est congru à l'un des nombres \(1, 2, \ldots, S\) modulo \(S + H\). Les nombres \(1, 2, \ldots, S + H\) sont appelés résidus. Pour deux résidus \(i\) et \(j\), une case est de type \((i, j)\) si l'indice de sa rangée est congru à \(i\) et celui de sa colonne à \(j\) modulo \(S + H\). On note \(v_{ij}\) le nombre de cases vicieuses de ce type.
Soient \(s\), \(s'\) deux variables parcourant les petits résidus et \(h\), \(h'\) deux variables parcourant les grands. Une case est de classe \(A\), \(B\), \(C\) ou \(D\) si son type est de la forme \((s, s')\), \((s, h)\), \((h, s)\) ou \((h, h')\) respectivement. On note \(a\), \(b\), \(c\), \(d\) les nombres de cases vicieuses de ces classes. Chaque case appartient à exactement une classe.
Affirmation 1.
Preuve. Considérons une petite rangée \(r\), et notons \(\alpha\) et \(\beta\) les nombres de ses cases vicieuses de classe \(A\) et \(B\). Comme dans la solution précédente, \(\alpha \geq S\) ou \(\beta \geq H\). Dans tous les cas, \(\frac{\alpha}{S} + \frac{\beta}{H} \geq 1\). En faisant cela pour chaque petite rangée et en additionnant, on obtient \(\frac{a}{S} + \frac{b}{H} \geq mS\). En échangeant rangées et colonnes, on obtient de même \(\frac{a}{S} + \frac{c}{H} \geq mS\). En additionnant ces inégalités et en divisant par \(2S\), on obtient l'affirmation. \(\square\)
Affirmation 2. Fixons deux petits résidus \(s\), \(s'\) et deux grands résidus \(h\), \(h'\). Alors \(2m - 1 \leq v_{ss'} + v_{sh'} + v_{hh'}\).
Preuve. Chaque serviette recouvre exactement une case de type \((s, s')\). En retirant toutes les serviettes qui recouvrent une case vicieuse de ce type, on obtient une autre collection de serviettes, qui recouvre chaque case de type \((s, s')\) soit \(0\) fois, soit \(M\) fois, selon que la case est vicieuse ou non. Il reste donc \((m^2 - v_{ss'})M\) serviettes, et dans toute la preuve de l'affirmation 2, on ne considère que ces serviettes restantes. Écrivons à l'encre rouge, dans chaque case, le nombre de ces serviettes qui la recouvrent. Une case dont le nombre rouge dépasse \(M\) est sûrement vicieuse.
Deux cases sont dites voisines si une même serviette peut les recouvrir toutes les deux. Chaque case de type \((h, h')\) a au plus quatre voisines de type \((s, s')\), tandis que chaque case de type \((s, h')\) a au plus deux voisines de chacun des types \((s, s')\) et \((h, h')\). Donc chaque nombre rouge d'une case de type \((h, h')\) ne dépasse pas \(4M\), et chaque nombre rouge d'une case de type \((s, h')\) ne dépasse pas \(2M\).
Soient \(x\), \(y\) et \(z\) les nombres de cases de type \((h, h')\) dont le nombre rouge appartient respectivement à \((M, 2M]\), \((2M, 3M]\) et \((3M, 4M]\). Toutes ces cases sont vicieuses, donc \(x + y + z \leq v_{hh'}\). Les nombres rouges des cases de type \((h, h')\) ont pour somme \((m^2 - v_{ss'})M\), puisque chaque serviette recouvre exactement une case de ce type. Il y a \((m - 1)^2\) cases de type \((h, h')\) ; en majorant chacun de ces nombres par un multiple de \(M\), on obtient
c'est-à-dire
Pour prouver l'affirmation, il suffit donc de montrer que \(y + 2z \leq v_{sh'}\).
Pour une case \(\delta\) de type \((h, h')\) et une case \(\beta\) de type \((s, h')\), on dit que \(\delta\) force \(\beta\) s'il y a plus de \(M\) serviettes recouvrant à la fois \(\delta\) et \(\beta\). Comme chaque nombre rouge d'une case de type \((s, h')\) ne dépasse pas \(2M\), une telle case ne peut être forcée par plus d'une case.
D'autre part, si le nombre rouge d'une case \((h, h')\) appartient à \((2M, 3M]\), elle force au moins une de ses voisines de type \((s, h')\) (puisque la somme des nombres rouges de leurs cases dépasse \(2M\)). De même, une case \((h, h')\) dont le nombre rouge est dans \((3M, 4M]\) force ses deux voisines de type \((s, h')\), puisque leurs nombres rouges ne dépassent pas \(2M\). Il y a donc au moins \(y + 2z\) cases forcées, et elles sont évidemment toutes vicieuses, comme voulu. \(\square\)
Affirmation 3.
Preuve. En faisant la moyenne du résultat précédent sur les \(S^2H^2\) quadruplets possibles \((s, s', h, h')\), on obtient \(2m - 1 \leq \frac{a}{S^2} + \frac{b}{SH} + \frac{d}{H^2}\). Par symétrie entre rangées et colonnes, la même estimation vaut avec \(b\) remplacé par \(c\). La moyenne de ces deux inégalités donne l'affirmation. \(\square\)
Multiplions maintenant (2) par \(H^2\), multiplions (1) par \(2SH - H^2\), et additionnons ; on obtient
Le membre de gauche vaut exactement \(H^2(m - 1) + 2SHm\), tandis que le membre de droite ne dépasse pas \(a + b + c + d\), puisque \(2H \leq S\). On obtient l'inégalité voulue. \(\blacksquare\)
Remarques¶
Remarque 2. L'affirmation 2 est la différence essentielle entre les deux solutions, car elle permet de se passer des notions de lignes riches et pauvres. On peut cependant la prouver aussi par la « méthode des fraises » : il suffit de mettre une fraise sur chaque case mauvaise pour une \(s\)-rangée, et une fraise sur chaque case mauvaise pour une \(h'\)-colonne. Chaque case porte alors au plus une fraise.
Remarque 3. Les deux solutions fonctionnent si le reste de la taille \(T\) de la table modulo la taille \(R\) des serviettes est au moins \(\frac{2}{3}R\), c'est-à-dire si \(T = Sm + H(m - 1)\) et \(R = S + H\) pour des entiers strictement positifs \(S\), \(H\), \(m\) tels que \(S \geq 2H\). Discutons les autres cas.
Cas 1. Si \(2H \geq S \geq \frac{H}{2}\), la borne optimale du nombre de cases vicieuses est \(mS^2 + (m - 1)H^2\) ; on l'obtient par les mêmes méthodes. Pour un exemple qui l'atteint, il suffit de retirer les serviettes de la troisième sorte de l'exemple de la solution 1 (avec un changement évident des nombres).
Cas 2. Si \(2S \leq H\), la situation est plus difficile. Si \((S + H)^2 > 2H^2\), la réponse et l'exemple sont les mêmes que dans le cas précédent ; sinon, la réponse est \((2m - 1)S^2 + 2SH(m - 1)\), et l'exemple est simplement donné par \((m - 1)^2\) serviettes disjointes.
Esquissons la preuve des deux estimations du cas 2, avec une notation plus adaptée tirée de la solution 2. Notons \(a^-\) et \(a^+\) les nombres de cases de classe \(A\) contenant un nombre strictement inférieur et strictement supérieur à \(M\) respectivement ; on définit \(b^\pm\), \(c^\pm\), \(d^\pm\) de même. Les preuves de l'affirmation 1 et des affirmations 2 et 3 mènent en fait aux inégalités
(pour la première, il faut considérer les grandes lignes au lieu des petites). En combinant ces inégalités, on obtient les estimations voulues. On peut aussi les prouver autrement, par exemple sans distinguer les cases riches et pauvres.