Zeigen Sie zu beliebigen n+2n+2n+2 ganzen Zahlen, dass es zwei davon gibt, deren Summe oder sonst deren Differenz durch 2n2n2n teilbar ist.

Beim Betrachten eines Putnam-Übungspapiers bin ich auf das folgende Problem gestoßen. Ich habe hier ähnliche Probleme gesehen, aber ich habe nicht das genaue gesehen. Ich würde gerne wissen, ob mein Beweis gültig ist.

Gegebenenfalls$n+2$ganze Zahlen zeigen, dass es zwei davon gibt, deren Summe oder auch Differenz durch teilbar ist$2n$.

Mein Versuch:

Nennen Sie die Menge von$n+2$ganze Zahlen$S$. Betrachten Sie die Kriterien, für die die Summe oder Differenz von$2$Elemente von$S$sind teilbar durch$2n$.

Lassen$a,b \in S$, so dass$a = nq_1 +r_1, b = nq_2 + r_2$.

Es folgt,$a+b = nq_1 +r_1 + nq_2 + r_2$

$= n(q_1 + q_2) + (r_1 + r_2)$

Fall$1$:$r_1 + r_2 = n$

$a+b = n(q_1+q_2) + n$ $= n(q_1 + q_2 + 1)$

$2n$wird dies teilen, wenn und nur wenn$q_1 + q_2 + 1 = 2k$für einige$k\in \mathbb{Z}$. Mit anderen Worten, es wird es teilen, wenn und nur wenn$q_1 + q_2 = 2k - 1$, also wenn$q_1 + q_2$ist ungerade.

Fall 2:$r_1 + r_2 = 0$

So,$a+b = nq_1 + nq_2$ $= n(q_1 + q_2)$Dies wird durch teilbar sein$2n$dann und nur dann, wenn$q_1 + q_2 = 2k$für einige$k\in \mathbb{Z}$.

Betrachten Sie die Situation beim ersten$n$Mitglieder von$S$haben einen eindeutigen Rest, wenn sie durch geteilt werden$n$. Nach dem Schubladenprinzip wird die$n+1$Mitglied von$S$ist kongruent zu einem dieser ersten$n$Mitglieder$\mod n$. Seit$|S| = n+2$, Die$n+2$Element von$S$müssen deckungsgleich sein$\mod n$zu einem der anderen Elemente von$S$. Wenn dies wäre$n+1$dann wäre Fall 2 oben notwendigerweise erfüllt. Dies liegt daran, dass wir die Terme subtrahieren könnten, um das Ergebnis zu erhalten, und von den drei Termen, die kongruent sind, muss die Summe oder Differenz eines solchen Paares ihrer Quotienten gerade sein.

Unter der Annahme, dass die Aussage falsch ist, folgt daraus, dass keine drei Terme kongruent sein können$\mod n$sonst wäre der Satz durch Fall 2 erfüllt. Es muss auch der Fall sein, dass es eine Teilmenge von gibt$S$mit$2$oder mehr Mitglieder, was deckungsgleich ist$z \mod n$, und es gibt eine weitere Teilmenge von$S$mit mindestens einem Mitglied, das kongruent ist$n-z \mod n$. Der Grund dafür ist, dass es sie gibt$\frac{n}{2}$mögliche Übereinstimmungen$\mod n$die diese Eigenschaft nicht erfüllen. Maximal$2$Elemente von$S$können für jede dieser möglichen Kongruenzen zugeordnet werden. So gibt es$2$Elemente verbleiben, und so ist die Eigenschaft erfüllt.

Forderung$U$die Teilmenge, die die beiden Mitglieder enthält, die kongruent sind$z \mod n$. Die Parität ihrer Quotienten muss unterschiedlich sein, sonst wäre Fall 2 erfüllt. Aber dann muss Fall 1 erfüllt sein, wegen des kongruenten Elements$n-z \mod n$. Dieses Element hat eine gewisse Parität und damit die Summe seines Quotienten mit dem Quotienten eines der Terme$U$muss seltsam sein. Alle Möglichkeiten sind ausgeschöpft, und damit ist die Theorie bewiesen.