Beweisidee oder Gegenbeispiel für Ungleichung gesucht

12.05.2015, 13:10

irre.flexiv

Hallo,

Ich bin neulich auf ein interessantes Problem gestoßen, das ich nicht lösen kann.

Gegeben je eine Partition zweier natürlicher Zahlen $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ mit der gleichen Anzahl an Summanden: $\begin{eqnarray*} A = a_1 + \dots + a_n \end{eqnarray*}$ und $\begin{eqnarray*} B = b_1 + \dots + b_n \end{eqnarray*}$

Gesucht ist nun eine Partition der Zahl $\begin{eqnarray*} S = \frac{A + B}{2} \end{eqnarray*}$ aus genau $\begin{eqnarray*} n \end{eqnarray*}$ Summanden der Partitionen von $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ . Es ist unmittelbar klar, dass $\begin{eqnarray*} 2|(A + B) \end{eqnarray*}$ notwendige Voraussetzung für die Existenz einer Lösung ist. Falls eine Lösung existiert, bilden die übrigen $\begin{eqnarray*} n \end{eqnarray*}$ Summanden zudem eine weitere Partition von $\begin{eqnarray*} S \end{eqnarray*}$ .

Nun zur Behauptung: Falls eine Lösung existiert und $\begin{eqnarray*} |A - B| > 0 \end{eqnarray*}$ , kann man immer $\begin{eqnarray*} a_i \end{eqnarray*}$ und $\begin{eqnarray*} b_j \end{eqnarray*}$ wählen so dass: $\begin{eqnarray*} |(A - a_i + b_j) - (B - b_j + a_i)| < |A - B| \end{eqnarray*}$ .

Diese Ungleichung beschreibt im Grunden einen Tausch der zwei Summanden $\begin{eqnarray*} a_i \end{eqnarray*}$ und $\begin{eqnarray*} b_j \end{eqnarray*}$ . Dieser sorgt dafür dass sich die Differenz der Summen verkleinert.

Ich konnte die Behauptung bis jetzt weder beweisen noch widerlegen und bin für jeden Hinweis dankbar. Falls sich die Behauptung beweisen lässt, ergibt sich daraus ein effizienter Algorithmus zur Lösung des Problems.

Zwei Beiträge zusammengefasst. Steffen

Vielleicht noch ein kleines Beispiel dazu:

$\begin{eqnarray*} S = 11 = 1 + 3 + 7 = 2 + 4 + 5 \end{eqnarray*}$

Tauscht man $\begin{eqnarray*} 1 \end{eqnarray*}$ mit $\begin{eqnarray*} 2 \end{eqnarray*}$ und $\begin{eqnarray*} 7 \end{eqnarray*}$ mit $\begin{eqnarray*} 5 \end{eqnarray*}$ erhält man:

$\begin{eqnarray*} A = 10 = 2 + 3 + 5 \end{eqnarray*}$

und

$\begin{eqnarray*} B = 12 = 1 + 4 + 7 \end{eqnarray*}$

Die Tausche rückgängig zu machen bringt in diesem Fall nichts, da sich so die Differenz der Summen erhöht. Allerdings kann man $\begin{eqnarray*} 3 \end{eqnarray*}$ und $\begin{eqnarray*} 4 \end{eqnarray*}$ tauschen und kommt so wieder auf die ursprünglichen Partitionen von $\begin{eqnarray*} S \end{eqnarray*}$ .

12.05.2015, 15:46

irre.flexiv

Auf diesen Beitrag antworten »

OK ich habe ein Gegenbeispiel konstruiert:

$\begin{eqnarray*} A = 728 = 300 + 411 + 11 + 6 \end{eqnarray*}$

und

$\begin{eqnarray*} B = 730 = 100 + 612 + 5 + 13 \end{eqnarray*}$

Grüße
irre.flexiv

12.05.2015, 15:51

HAL 9000

Auf diesen Beitrag antworten »

Inwiefern soll das ein Gegenbeispiel zu der zu beweisenden Implikation

Zitat:

Original von irre.flexiv
Behauptung: Falls eine Lösung existiert und $\begin{eqnarray*} |A - B| > 0 \end{eqnarray*}$ , kann man immer $\begin{eqnarray*} a_i \end{eqnarray*}$ und $\begin{eqnarray*} b_j \end{eqnarray*}$ wählen so dass: $\begin{eqnarray*} |(A - a_i + b_j) - (B - b_j + a_i)| < |A - B| \end{eqnarray*}$ .

sein? Soweit ich erkenne, existiert für dein Beispiel keine Lösung im obigen Sinne, damit ist schon mal ausgeschlossen, dass man mit diesem Beispiel die Implikation widerlegen kann. verwirrt

12.05.2015, 16:14

irre.flexiv

Auf diesen Beitrag antworten »

Es existiert eine Lösung. Man tausche zum Beispiel $\begin{eqnarray*} 11 \end{eqnarray*}$ mit $\begin{eqnarray*} 5 \end{eqnarray*}$ und $\begin{eqnarray*} 6 \end{eqnarray*}$ mit $\begin{eqnarray*} 13 \end{eqnarray*}$ und erhält:

$\begin{eqnarray*} 729 = 300 + 411 + 5 +13 \end{eqnarray*}$

und

$\begin{eqnarray*} 729 = 100 + 612 + 11 + 6 \end{eqnarray*}$

Und egal welchen der 16 möglichen Tausche man als erstes wählt, die Differenz erhöht sich oder bleibt gleich.

12.05.2015, 16:17

HAL 9000

Auf diesen Beitrag antworten »

Ach Ok, danke - hatte ich übersehen. Freude

Neue Frage »

Antworten »

Beweisidee oder Gegenbeispiel für Ungleichung gesucht

Verwandte Themen