Shortlist 2014, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Serbia
Concepts : Double comptage · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2014 (avec solutions), p. 26 (page 27 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Let \(n\) points be given inside a rectangle \(R\) such that no two of them lie on a line parallel to one of the sides of \(R\). The rectangle \(R\) is to be dissected into smaller rectangles with sides parallel to the sides of \(R\) in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect \(R\) into at least \(n + 1\) smaller rectangles.
Indices : les idées clés
- Double comptage (solution 1) : en comptant les coins des \(k\) rectangles, \(4k = 4 + 2b + 4c\), où \(b\) est le nombre de « T » et \(c\) le nombre de croisements ; donc \(b \leq 2k - 2\).
- Chaque point donne deux « T » : le segment de bord qui porte un point, prolongé au maximum, se termine par deux « T », et deux points ne partagent pas de « T » ; donc \(b \geq 2n\).
- Récurrence sur le nombre de rectangles (solution 2) : on retire ce qui est sous la plus basse droite horizontale de découpe.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (deux solutions).
Solution 1¶
Soit \(k\) le nombre de rectangles du découpage. L'ensemble des points qui sont des coins d'au moins un rectangle se partage en trois sous-ensembles disjoints :
- \(A\), formé des quatre coins du rectangle \(R\), dont chacun est le coin d'exactement un des petits rectangles ;
- \(B\), formé des points où exactement deux rectangles ont un coin commun (les « T », voir la figure) ;
- \(C\), formé des points où quatre rectangles ont un coin commun (les croisements, voir la figure).
Notons \(b\) le nombre de points de \(B\) et \(c\) celui de \(C\). Chacun des \(k\) rectangles a exactement quatre coins, donc
Il s'ensuit que \(2b \leq 4k - 4\), soit \(b \leq 2k - 2\).
Chacun des \(n\) points donnés est sur un côté d'un des petits rectangles (mais pas sur un côté de \(R\)). En prolongeant ce côté le plus loin possible le long des frontières entre rectangles, on obtient un segment dont les deux extrémités sont des « T ». Chaque point de \(B\) est l'extrémité d'au plus un tel segment contenant un point donné, puisque deux points donnés ne sont jamais sur une même droite parallèle aux côtés de \(R\). Donc
En combinant les deux inégalités, on obtient \(2k - 2 \geq b \geq 2n\), donc \(k \geq n + 1\). \(\blacksquare\)
Solution 2¶
Soit \(k\) le nombre de rectangles. On appelle « horizontale » et « verticale » les directions des côtés de \(R\). Pour \(n\) fixé, on veut montrer \(k \geq n + 1\) ; de façon équivalente, on montre \(n \leq k - 1\) pour tout \(k\), par récurrence sur \(k\). Pour \(k = 1\), c'est évident.
Supposons \(k > 1\). Si aucun des segments qui séparent les rectangles n'est horizontal, on a \(k - 1\) segments verticaux qui découpent \(R\) en \(k\) rectangles. Chacun d'eux porte au plus un des \(n\) points, donc \(n \leq k - 1\), comme voulu.
Sinon, considérons la plus basse droite horizontale \(h\) qui contient un ou plusieurs de ces segments. Soit \(R'\) le rectangle obtenu en retirant de \(R\) tout ce qui est sous \(h\) (voir l'exemple de la figure).
Les rectangles situés entièrement sous \(h\) forment des blocs séparés par des segments verticaux. Supposons qu'il y ait \(r\) blocs, et \(k_i\) rectangles dans le \(i\)-ème bloc. Les bords gauche et droit de chaque bloc se prolongent au-dessus de \(h\). On peut donc faire monter les points situés sur ces bords pour qu'ils soient dans \(R'\), sans violer les conditions : il suffit de veiller à ce qu'ils ne se retrouvent pas sur une même horizontale qu'un autre point donné.
Toutes les autres frontières entre rectangles du \(i\)-ème bloc sont entièrement sous \(h\). Il y en a \(k_i - 1\), et chacune porte au plus un des points donnés. Enfin, il peut y avoir un point sur \(h\). Tous les autres points sont dans \(R'\) (après les déplacements ci-dessus).
Le rectangle \(R'\) est découpé en \(k - \sum_{i=1}^r k_i\) rectangles. Par l'hypothèse de récurrence appliquée à \(R'\), il y a au plus
points. Comme \(r \geq 1\), on a \(n \leq k - 1\), ce qui achève la récurrence. \(\blacksquare\)