Potrzebne jest wyjaśnienie rozwiązania problemu kombinatoryki obejmującego kwadraty o równoległych bokach

Question

Niech skończona liczba kwadratów o równoległych bokach w płaszczyźnie, taka, że ​​jeśli istnieją $k+1$ kwadraty są wybrane, a następnie istnieją $2$przecinające się kwadraty między nimi. Udowodnij, że kwadraty można pogrupować$2k-1$ zestawy takie, że przecinają się dowolne dwa kwadraty w tym samym zestawie.

Znalazłem ten problem na AOPS, ale nie mogłem zrozumieć rozwiązania.

https://artofproblemsolving.com/community/q1h1805602p12209708

To jest link. Nie mogłem właściwie zrozumieć, dlaczego „kwadraty, które przecinają się z$ABCD$ albo zawiera punkt $B$ lub punkt $C$ lub oba. ”(jak jest napisane w ostatnim komentarzu do posta). Czy możesz mnie oświecić? A jeśli problem jest zły, czy mógłbyś mi pomóc z kontrprzykładem? Dziękuję bardzo!

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

Answer 1

W pytaniu postawionym na AoPS jest dodatkowe założenie, że wszystkie kwadraty są przystające; bez utraty ogólności możemy przyjąć długość boku jako$1$. $ABCD$w rozwiązaniu tam przedstawionym jest (jednym z) skrajnych lewych kwadratów w kolekcji; powiedz, że jego lewy dolny róg ma współrzędne$(x,y)$. Następnie dowolny kwadrat$S$ krzyżujący $ABCD$ musi mieć lewy dolny róg $(u,v)$ gdzie $x\le u\le x+1$ (od $ABCD$ to kwadrat z lewej strony) i $y-1\le v\le y+1$.

Łatwo to pokazać, jeśli $y-1\le v\le y$ następnie $S$ zawiera $C$; Jeśli$y\le v\le y+1$ następnie $S$ zawiera $B$. A zatem$S$ zawsze będzie zawierać co najmniej jeden z $B$ i $C$.