Wählen Sie 8 verschiedene ganze Zahlen aus {1,2,…,16,17}{1,2,…,16,17}\{1, 2,\dots,16,17\}. Zeigen Sie, dass die Acht mindestens drei Paare mit einem gemeinsamen Unterschied für _irgendeine_ Wahl enthalten.

Dieses Problem stammt von der kanadischen Nationalolympiade 1999. Ich stecke fest und versuche, den ersten Teil mit dem Schubladenprinzip zu beweisen. Gibt es eine Verfeinerung, die eine schärfere Verwendung ermöglicht, oder gibt es eine clevere Verwendung der Parität, die Teil 1 beweisen würde? oder ein anderer ansatz?

Was Teil 2 betrifft, stelle ich mir vor, dass sich eine Lösung ganz natürlich aus der Lösung von Teil 1 ergeben wird.

Vermuten$a_1,a_2,\dots,a_8$sind acht verschiedene ganze Zahlen aus$\{1,2,\dots,16,17\}$. Zeigen Sie, dass es eine ganze Zahl gibt$k>0$so dass die Gleichung

$a_i−a_j=k \tag{1}$

hat mindestens drei verschiedene Lösungen.

---

Finden Sie auch einen bestimmten Satz von 7 verschiedenen ganzen Zahlen aus$\{1,2,\dots,16,17\}$so dass die Gleichung$a_i−a_j=k$hat für keine drei verschiedene Lösungen$k>0$.

Angenommen, die ausgewählten$a_n$sind so bestellt$a_1<a_2<\dots<a_8$. Definieren Sie die 1-Lücken zwischen aufeinanderfolgenden Termen als

$\alpha_n = a_{n+1}-a_n,\: 1 \le n \le 7 \tag{2}$

Ganz klar diese sieben$\alpha_k$kann höchstens 16 ergeben. Wenn drei dieser 1-Lücken den gleichen Wert haben,$k$, dann hat Gleichung (1) drei Lösungen dafür$k$, das muss also vermieden werden. Um diese beiden Bedingungen zu erfüllen

$(\alpha_1,\alpha_2,\dots,\alpha_7)\text{ must be a permutation of }(1,1,2,2,3,3,4) \tag{3}$

Um das Schubladenprinzip anzuwenden, definieren Sie nun die 2-Lücken

$\beta_n = a_{n+2}-a_n,\:\text{ for }1 \le n \le 6 \tag{4}$

Diese beziehen sich auf die 1-Lücken als$\beta_n = \alpha_n + \alpha_{n+1},\:\text{ for }1 \le n \le 6 \tag{5}$

Es gibt sechs 2-Lücken, und sie können solche Werte für alle haben$n$

$4 \le \beta_n \le 7 \tag{6}$

Wir können nur einen davon haben$\beta_n=4$, da es eine gibt$\alpha_n=4$. Da zwei verschiedene$\beta_n$denselben Wert teilen können (z$5,6,7$), gibt es also sieben Slots und nur sechs zu platzierende Objekte, sodass das Schubladenprinzip nicht drei Lösungen für Gleichung (1) erzwingt.