Taubenschlagprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:54 Di 10.04.2007 | | Autor: | mimi1310 |
| Aufgabe | In einem Garten gibt es 4 Steinhaufen. Bei einer Umgestaltung werden die 4 Haufen in fünf Haufen umverteilt. Zeigen Sie, dass es 2 Steine gibt, welche in einem kleineren Steinhaufen zu liegen kommen.
Hinweis: Ordnen Sie die alten und neuen Steinhaufen in absteigender Reihenfolge und vergleichen Sie die Anzahl der Steine in den ersten k Haufen der ursprünglichen Aufteilung und der neuen Aufteilung mit k=1,2,3,4 |
Hallo!
Also mir ist klar, dass ich diese Aufgabe irgendwie mit dem Taubenschlagprinzip lösen muss, aber mit dem Hinweis kann ich echt nichts abfangen, ich verstehe absolut nicht was ich da machen muss.
Vielen Dank im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:21 Di 10.04.2007 | | Autor: | wauwau |
[mm] a_{1} \ge a_{2} \ge a_{3} \ge a_{4} [/mm] Anzahl der Steine in den vier Steinhaufen vor Umordnung
[mm] b_{1} \ge b_{2} \ge b_{3} \ge b_{4} \ge b_{5} [/mm] mit [mm] b_{i} \ge [/mm] 1
mit
[mm] a_{1} [/mm] + [mm] a_{2} [/mm] + [mm] a_{3} [/mm] + [mm] a_{4} [/mm] = [mm] b_{1} [/mm] + [mm] b_{2} [/mm] + [mm] b_{3} [/mm] + [mm] b_{4} [/mm] + [mm] b_{5}
[/mm]
Fall 1) kein Stein kommt in einem Steinhaufen mit weniger Steinen zu liegen
dann würde gelten [mm] b_{i} \ge a_{i} [/mm] und da [mm] b_{5} \ge [/mm] 1 kann obige Gleichung nicht gelten
Fall 2) ein Stein kommt in einem STeinhaufen mit weniger STeinen zu liegen alle anderen in Haufen mit mindestens gleich viel.
[mm] b_{1} [/mm] + [mm] b_{2} [/mm] + [mm] b_{3} [/mm] + [mm] b_{4} [/mm] + [mm] b_{5} \ge a_{1} [/mm] + [mm] a_{2} [/mm] + [mm] a_{3} [/mm] + [mm] a_{4}+1 [/mm] was auch nicht möglich wäre
daher Fall 3) mindestens zwei Steine
|
|
|
| |
|
Hallo!
Erstmal vielen vielen Dank, das mit den Fällen verstehe ich auch alles nur eine Stelle nicht so ganz:
"...dann würde $ [mm] b_{i} \ge a_{i} [/mm] $ gelten und da $ [mm] b_{5} \ge [/mm] $ 1 kann obige Gleichung nicht gelten..."
Das verstehe ich noch nicht so ganz.
Lg
|
|
|
| |
|
Hallo mimi1310!
> Hallo!
> Erstmal vielen vielen Dank, das mit den Fällen verstehe
> ich auch alles nur eine Stelle nicht so ganz:
> "...dann würde [mm]b_{i} \ge a_{i}[/mm] gelten und da [mm]b_{5} \ge[/mm] 1
> kann obige Gleichung nicht gelten..."
> Das verstehe ich noch nicht so ganz.
> Lg
Ich glaube, das ist etwas "schlecht formuliert". Soweit ich das verstehe, ist gemeint, dass also in diesem Fall ja [mm] b_i\ge a_i [/mm] sein muss, für alle i. Für die ersten 4 geht das auch noch, da aber insgesamt die a-Haufen genauso viele Steine haben wie die b-Haufen, dürfte der 5. Haufen höchstens 0 Steine, oder halt eine negative Anzahl an Steinen haben. (genau 0, falls alle anderen b-Haufen genauso groß sind wie die a-Haufen, und z. B. -4, wenn jeder der b-Haufen um genau einen Stein größer ist als der entsprechende a-Haufen).
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Do 12.04.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
