Benötigen Sie eine Erklärung zur Lösung eines kombinatorischen Problems mit Quadraten mit parallelen Seiten

Question

Lassen Sie eine endliche Anzahl von Quadraten mit parallelen Seiten in der Ebene, so dass, falls vorhanden $k+1$ Quadrate werden ausgewählt, dann existieren sie $2$sich kreuzende Quadrate zwischen ihnen. Beweisen Sie, dass die Quadrate in Gruppen eingeteilt werden können$2k-1$ setzt so, dass sich zwei beliebige Quadrate in derselben Menge schneiden.

Ich habe dieses Problem bei AOPS gefunden, aber ich konnte die Lösung nicht verstehen.

https://artofproblemsolving.com/community/q1h1805602p12209708

Das ist die Verbindung. Ich konnte nicht richtig verstehen, warum "Quadrate, die sich überschneiden$ABCD$ entweder enthält Punkt $B$ oder Punkt $C$ oder beides. "(wie es im letzten Kommentar zum Beitrag geschrieben steht). Können Sie mich bitte aufklären? Oder wenn das Problem falsch ist, können Sie mir bitte mit einem Gegenbeispiel helfen? Vielen Dank!

https://math.stackexchange.com/questions/3923791/need-counterexample-on-a-combinatorics-problem

Answer 1

Es gibt die zusätzliche Annahme in der Frage, wie sie auf AoPS gestellt wird, dass die Quadrate alle kongruent sind; ohne Verlust der Allgemeinheit können wir die Seitenlänge als nehmen$1$. $ABCD$ist in der dort bereitgestellten Lösung (eines der) Quadrate ganz links in der Sammlung; Sagen Sie, dass die untere linke Ecke Koordinaten hat$(x,y)$. Dann irgendein Quadrat$S$ sich überschneiden $ABCD$ muss die untere linke Ecke haben $(u,v)$ wo $x\le u\le x+1$ (schon seit $ABCD$ ist das am weitesten links stehende Quadrat) und $y-1\le v\le y+1$.

Es ist leicht zu zeigen, dass wenn $y-1\le v\le y$ dann $S$ enthält $C$;; wenn$y\le v\le y+1$ dann $S$ enthält $B$. So$S$ wird immer mindestens eine von enthalten $B$ und $C$.