Problem liczenia dotyczący uogólnionej zasady gołębia
W grze wszystkie punkty na płaszczyźnie (x, y) z zachowaniem współrzędnych $ x, y \in \mathbb{Z} $ są oznaczone jako należące do jednego z trzech graczy, tj. Alice, Bob lub Carol.
Pokaż, że jeden z graczy będzie posiadał cztery punkty, których wierzchołki tworzą prostokąt.
Oto problem, o którym myślę od wielu dni. Wydaje się to łatwe, ponieważ współrzędne są nieograniczone. Ale trudno też znaleźć przegródki, które chcę podzielić.
Napotkałem kilka problemów, takich jak znalezienie równoległoboku na $n \times n$ szachownica z $2n$pionki. Dla mnie jest to stosunkowo prostsze.
Odpowiedzi
WSKAZÓWKA: Rozważ punkty $\langle 0,n\rangle$, $\langle 1,n\rangle$, $\langle 2,n\rangle$, i $\langle 3,n\rangle$ dla $n=0,1,2,\ldots\;$. Wyobraź sobie, że każdy punkt jest oznaczony$A$, $B$lub $C$. W ten sposób jeden wiersz może zostać oznaczony$ABCA$, inny może być oznaczony $BCCB$, i tak dalej.
- Ile różnych etykiet w jednym rzędzie jest możliwych?
- Dlaczego chciałbyś znaleźć dwa wiersze z tą samą etykietą?
- Ile potrzeba wierszy, aby zagwarantować, że masz dwa wiersze z tym samym etykietą?