Gegeben sei eine Menge \(M = \{ m_1, m_2, \dots, m_n \}\) mit \(n\) positiven ganzen Zahlen und eine ganze Zahl \(1 \le k < n\). Gesucht ist eine \(k\)-elementige Teilmenge \(I \subset M\), sodass
$$\sum_{i \in I} \sum_{j \in J} |i - j|$$
mit \(J = M \setminus I\) minimal ist. Ich habe herausgefunden, dass folgende Wahl von \(I\) optimal zu sein scheint: Ist oBdA \(m_1 < m_2 < \dots < m_n\) und \(2k < n\), dann finde einen Index \(s\), sodass \(\max(s, n - (s + 2(k - 1)))\) minimal ist und setze \(I = \{ m_s, m_{s + 2}, m_{s + 4}, \dots, m_{s + 2(k - 1)} \}\).
Frage: Stimmt die Vermutung und wie kann ich sie beweisen?
Bisher kann ich nur für den Fall \(k = 1\) argumentieren. Ist nämlich \(m_s\) das einzige Element von \(I\), dann ist die zu minimierende Summe gleich
$$\sum_{j = 1}^n |m_j - m_s|$$
und der Median \(m_{\left\lfloor \frac{n}{2} \right\rfloor}\) leistet das Gewünschte, man wählt also \(s = \left\lfloor \frac{n}{2} \right\rfloor\) (wofür auch \(\max(s, n - s)\) minimal ist). Wählt man nämlich ein Element größer oder kleiner als der Median, dann vergrößert sich die Differenz zu mehr Zahlen als sie sich verkleinert und die Summe wird größer.
Hat jemand eine kluge Idee?
