Warum reduziert man bei der Summe über die Minima alle verbleibenden Folgeglieder?

Question

Hallo zusammen,
folgende Herausforderung, wobei ich hier vermutlich nur irgendwo einen Knoten hab, der gelöst werden muss damit der Rest nachrutscht.
Thema:

Satz von Erdös und Gallai.

Gegeben ist eine Folge (10, 9, 8, 7, 6, 5, 4, 3, 3, 3, 2)

Da es sich um einen Satz handelt, welcher mehrere Schritte beinhaltet, von denen die ersten aber klar verstanden wurden (Partitionierung und Summe der ersten 3 Zahlen), fehlt nun ein Rechenschritt, welcher zum Verbleib der Folge (7,6,5,4,3,3,3,2) und der Ungleichung.

27 ≤    3*2 +  $$\sum \limits_{n=3}^{11} min\{3,4\}$$

Gelöst hab ich die Aufgabe richtig (27 ≤ 29) , allerdings habe ich eine Verständnisfrage:

Warum reduziert man bei der Summe über die Minima alle verbleibenden Folgeglieder >3 auf 3?

Denn der Ansatz aus (7,...,3,2)  ->  7*3 + 1*2 zu machen, scheint zur Lösung geführt zu haben. Verstanden hab ich den Ansatz aber nicht.

Wäre dann analog die Summe über die Maxima {8,7} der Folge 9,8,7,6,5,4,3 die Summe 1*9 + 6*8?

Und der Name ist schon richtig gewählt. Ich tendiere dazu um 2 Ecken zu viel oder zu wenig zu denken.

Viele Grüße

Comments

Hallo

es ist völlig unklar, was da eigentlich gezeigt werden soll?

27<3*2+(11-2)*3  gibt bei mir 6+27=33 nicht 29.

dass die Summe über 9,8,7,6,5,4,3<9+6*8 ist

Aber was du eigentlich willst ist mir unklar, warum diese Summen über eine endliche Zahl von ganzen Zahlen, die man leicht bestimmen kann? Wozu die Ungleichungen?

auch  sehe ich nicht was das mit Satz von Erdös und Gallai direkt zu tun hat?

lul

---

Okay sorry.

Ich hätte wohl nicht in der Mitte anfangen sollen.

Satz von Erdös und Gallai.

$$ \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)$$

Anzuwenden auf Valenzsequenz d_i (10, 9, 8, 7, 6, 5, 4, 3, 3, 3, 2)

Ich wähle die ersten 3 Elemente um sie vom Rest abzusplitten (würde auch mit 2, mit 4 oder oder oder... funktionieren)

also

$$ \sum _{i=1}^{3}d_{i}\leq 3(3-1)+\sum _{i=3+1}^{n}\min(d_{i},3)$$

und damit

 $$10+9+8 = 27 \leq 3(3-1)+\sum _{i=3+1}^{n}\min(d_{i},3)$$

Und beim genauen hinschreiben ist mir nun der Knoten im Hirn klar geworden.

Ich hatte d_i im Kopf nicht weitergezählt.

Fangen wir bei d_4 an (also 7) ist das min{7,3} klar, also

3+min{6,3}...usw. Dass die 2 am ende dazugezählt wird ist nun auch klar, da min{2,3} eigentlich offensichtlich sein sollte. Jedenfalls wenn man sich an die Ordnungsaxiome halten will.

Damit hat sich das ganze erledigt. :)

---

schön für dich, damit ist die Frage erledigt?

lul

Answer 1

Fragender hat selbst die Lösung gefunden, sieh vorletzter Kommentar

lul