Schubfachprinzip

16.02.2022, 20:52	SehnigerAdrian	Auf diesen Beitrag antworten »
Schubfachprinzip Meine Frage: Wir schreiben jede Zahl 1,2,3...17 in Quadrate des 17x17-Gitters, so dass jede Zahl 17 Mal geschrieben wird. Beweisen Sie, dass es eine Zeile oder eine Spalte gibt, in der es mindestens fünf verschiedene Zahlen gibt. Meine Ideen: Wie kann ich an diese Aufgabe herangehen. Soll als Vorbereitung zur Matheolympiade dienen,aber ich komme nicht weiter
16.02.2022, 23:07	HAL 9000	Auf diesen Beitrag antworten »
Ist wirklich etwas tricky - ich hab (mit Unterbrechungen) fast eine Stunde dran gerätselt... 1) Die Zahl $\begin{eqnarray} k \end{eqnarray}$ möge in genau $\begin{eqnarray} z_k \end{eqnarray}$ Zeilen sowie $\begin{eqnarray} s_k \end{eqnarray}$ Spalten vorkommen. Die Annahme $\begin{eqnarray} z_k+s_k\leq 8 \end{eqnarray}$ führt dazu, dass es maximal $\begin{eqnarray} z_ks_k\leq \left(\frac{z_k+s_k}{2}\right)^2 \leq 16 \end{eqnarray}$ Felder mit Zahl $\begin{eqnarray} k \end{eqnarray}$ geben kann, Widerspruch. Wenn wir die Menge der Zeilen und Spalten mit $\begin{eqnarray} M_k \end{eqnarray}$ bezeichnen, dann ist somit $\begin{eqnarray} \|M_k\|=z_k+s_k\geq 9 \end{eqnarray}$ . 2) Über alle 17 Zahlen betrachtet haben wir in $\begin{eqnarray} M_1,\ldots,M_{17} \end{eqnarray}$ mindestens $\begin{eqnarray} 9\cdot 17=153 \end{eqnarray}$ Nennungen von Zeilen oder Spalten. Da es aber nur 34 Zeilen und Spalten gibt, muss es mindestens eine Zeile oder Spalte mit mindestens $\begin{eqnarray} \left\lceil \frac{153}{34}\right\rceil = 5 \end{eqnarray}$ Nennungen geben, und jede dieser 5 Nennungen gehört zu einer verschiedenen Zahl - fertig.
17.02.2022, 15:29	SehnigerAdrian	Auf diesen Beitrag antworten »
Vielen Dank. Dann kann man ja das ganze verallgemeinern auf ein n×n Brett, sodass immer mindestens $\begin{eqnarray} \left \lceil{\sqrt{n}}\right \rceil \end{eqnarray}$ zahlen in einer Spalte/Zeile vorkommen
17.02.2022, 15:39	HAL 9000	Auf diesen Beitrag antworten »
Kann man so sagen, ja. Zumindest im Fall $\begin{eqnarray} n=m^2 \end{eqnarray}$ ist ja nicht schwer, eine Zahlenverteilung mit genau $\begin{eqnarray} m \end{eqnarray}$ verschiedenen Zahlen in JEDER Spalte und Zeile zu finden. Bei $\begin{eqnarray} n=17 \end{eqnarray}$ ist schon ein wenig Bastelei nötig eine Zahlenverteilung zu finden, wo in jeder Zeile und Spalte maximal 5 verschiedene Zahlen anzutreffen sind - aber es geht.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »