Besoin d'explications sur la solution d'un problème combinatoire impliquant des carrés à côtés parallèles
Soit un nombre fini de carrés avec des côtés parallèles dans le plan, de sorte que le cas échéant $k+1$ les carrés sont choisis, alors il existe $2$carrés qui se croisent entre eux. Prouvez que les carrés peuvent être regroupés en$2k-1$ ensembles tels que deux carrés du même ensemble se croisent.
J'ai trouvé ce problème sur AOPS, mais je ne pouvais pas comprendre la solution.
https://artofproblemsolving.com/community/q1h1805602p12209708
Voici le lien. Je ne comprenais pas correctement pourquoi "Les carrés qui se croisent avec$ABCD$ soit contient un point $B$ ou point $C$ ou les deux. "(comme il est écrit dans le dernier commentaire du message). Pouvez-vous m'éclairer s'il vous plaît? Ou si le problème est erroné, pourriez-vous s'il vous plaît m'aider avec un contre-exemple? Merci beaucoup!
https://math.stackexchange.com/questions/3923791/need-counterexample-on-a-combinatorics-problem
Réponses
Il y a l'hypothèse supplémentaire dans la question posée sur AoPS que les carrés sont tous congruents; sans perte de généralité, nous pouvons prendre la longueur du côté comme$1$. $ABCD$est, dans la solution qui y est fournie, (l'un des) carrés les plus à gauche de la collection; dire que son coin inférieur gauche a des coordonnées$(x,y)$. Puis n'importe quel carré$S$ sécante $ABCD$ doit avoir un coin inférieur gauche $(u,v)$ où $x\le u\le x+1$ (depuis $ABCD$ est le carré le plus à gauche) et $y-1\le v\le y+1$.
Il est facile de montrer que si $y-1\le v\le y$ puis $S$ contient $C$; si$y\le v\le y+1$ puis $S$ contient $B$. Donc$S$ contiendra toujours au moins un des $B$ et $C$.