Mo 451343

08.09.2011, 20:22

Kev11

Mo 451343

Man untersuche, für welche positiven ganzen Zahlen n es möglich ist, die Punkte 1,2,3,...,2n der Zahlengeraden so mit n Farben zu färben, dass jede Farbe genau zweimal vorkommt und jede positive ganze Zahl von 1 bis n genau einmal als Abstand gleichfarbiger Punkte auftritt.

Kann jemand von euch diese Aufgabe lösen?
Ich vermute die ersten n sind:
1, 4, 5, 9, 16, 40, 81, 221, 460, 1276, 2669, 7425, 15544, 43264, 90585, 252149, ...

08.09.2011, 21:01

Airblader

Auf diesen Beitrag antworten »

Kleiner Hinweis: Die Aufgabe (klick) stammt aus der MO von 2005/2006, ist also aus keinem aktuellen Wettbewerb.

air

09.09.2011, 07:34

René Gruber

Auf diesen Beitrag antworten »

Dass es für $\begin{eqnarray*} n\equiv 2\bmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} n\equiv 3\bmod 4 \end{eqnarray*}$ nicht klappt, kann man sich leicht über geeignete Summen- bzw. Differenzbetrachtungen überlegen.

Für alle anderen $\begin{eqnarray*} n \end{eqnarray*}$ (also $\begin{eqnarray*} n\equiv 0\bmod 4 \end{eqnarray*}$ oder $\begin{eqnarray*} n\equiv 1\bmod 4 \end{eqnarray*}$ ) klappt es aber, wie man dann durch Angabe einer jeweils geeigneten Färbung nachweisen kann, als Beispiel mal so eine Färbung für das in deiner Liste fehlende n=8:

(4,5)
(11,13)
(3,6)
(12,16)
(10,15)
(2,8)
(7,14)
(1,9)

Insofern ist deine Liste ziemlich lückenhaft.

09.09.2011, 21:20

Kev11

Auf diesen Beitrag antworten »

Ja, ich hatte schon vermutet, dass eine lückenhafte Lösungsvermutung der Grund für das Scheitern meines Beweisversuches ist. Ich konnte mich aber nicht befreien, danke dass du mir geholfen hast :-).

08.10.2011, 13:29

eva_c

Auf diesen Beitrag antworten »

Hallo,
ich finde diese Aufgabe sehr interessant. Aber ich sehe nicht wie man leicht zeigen kann, dass es für n==2 mod 4 und n==3 mod 4 nicht klappt. Kann mir das jemand erklären?
Gruß Eva

08.10.2011, 15:20

René Gruber

Auf diesen Beitrag antworten »

Bei einer konkreten Färbung hast du zu jeder Farbe zwei Zahlen, die mit dieser Farbe gefärbt werden, eine kleinere und eine größere. Sei nun $\begin{eqnarray*} A \end{eqnarray*}$ die Menge der $\begin{eqnarray*} n \end{eqnarray*}$ kleineren und $\begin{eqnarray*} B \end{eqnarray*}$ die Menge der $\begin{eqnarray*} n \end{eqnarray*}$ größeren Zahlen dieser Färbung, sowie außerdem $\begin{eqnarray*} a \end{eqnarray*}$ die Summe aller Zahlen aus $\begin{eqnarray*} A \end{eqnarray*}$ sowie $\begin{eqnarray*} b \end{eqnarray*}$ die Summe aller Zahlen aus $\begin{eqnarray*} B \end{eqnarray*}$ .

Es ist $\begin{eqnarray*} A\cup B = \{1,2,\ldots,2n\} \end{eqnarray*}$ und somit

$\begin{eqnarray*} a+b = \sum_{k=1}^{2n} k = \frac{2n(2n+1)}{2} = n(2n+1)\qquad (1) \end{eqnarray*}$

Andererseits lässt sich Bedingung

Zitat:

Original von Kev11
jede positive ganze Zahl von 1 bis n genau einmal als Abstand gleichfarbiger Punkte auftritt.

in die Gleichung

$\begin{eqnarray*} b-a = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}\qquad (2) \end{eqnarray*}$

übersetzen. Das Gleichungssystem (1)(2) kann man lösen, wobei u.a.

$\begin{eqnarray*} a = \frac{n(3n+1)}{4} \qquad (3) \end{eqnarray*}$

herauskommt. Nun muss aber $\begin{eqnarray*} a \end{eqnarray*}$ eine ganze Zahl sein, was für $\begin{eqnarray*} n\equiv 2\bmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} n\equiv 3\bmod 4 \end{eqnarray*}$ in Lösung (3) nicht der Fall ist - also kann es für derartige $\begin{eqnarray*} n \end{eqnarray*}$ keine solche Färbung geben.

08.10.2011, 17:22

eva_c

Auf diesen Beitrag antworten »

Vielen Dank für diese gute Erklärung!
Gruß Eva

Neue Frage »

Antworten »

Mo 451343

Verwandte Themen