Zählproblem bezüglich des generalisierten Pigeonhole-Prinzips

Nov 19 2020

In einem Spiel werden alle Punkte in der (x, y) -Ebene mit den Koordinaten eingehalten $ x, y \in \mathbb{Z} $ sind als zu einem von drei Spielern gehörend gekennzeichnet, dh entweder zu Alice, Bob oder Carol.

Zeigen Sie, dass einer der Spieler vier Punkte besitzt, deren Eckpunkte ein Rechteck bilden.

Hier ist das Problem, über das ich seit Tagen nachgedacht habe. Es scheint einfach zu sein, da die Koordinaten unbegrenzt sind. Es ist aber auch schwierig, Schubladen zu finden, die ich teilen möchte.

Ich habe verschiedene Probleme festgestellt, z. B. das Finden eines Parallelogramms auf einem $n \times n$ Schachbrett mit $2n$Bauern. Es ist relativ einfach für mich.

Antworten

5 BrianM.Scott Nov 20 2020 at 02:57

TIPP: Betrachten Sie die Punkte $\langle 0,n\rangle$, $\langle 1,n\rangle$, $\langle 2,n\rangle$, und $\langle 3,n\rangle$ zum $n=0,1,2,\ldots\;$. Stellen Sie sich vor, jeder Punkt ist beschriftet$A$, $B$, oder $C$. Somit könnte eine Zeile beschriftet sein$ABCA$könnte ein anderer beschriftet sein $BCCB$, und so weiter.

  • Wie viele verschiedene Beschriftungen einer Reihe sind möglich?
  • Warum möchten Sie zwei Zeilen mit derselben Beschriftung finden?
  • Wie viele Zeilen sind erforderlich, um sicherzustellen, dass Sie zwei Zeilen mit derselben Beschriftung haben?