Schubfachprinzip |
| 06.01.2014, 14:39 | ter11 | Auf diesen Beitrag antworten » |
| Schubfachprinzip Der Nikolaus hat ingesamt 16 verschiedene Geschenke, welche alle einen Wert zwischen 1 und 4000 Euro haben. Zufalligerweise haben keine zwei der 16 Geschenke denselben Wert. Sein Problem: Er muss die Geschenke so auf zwei Kinder aufteilen, dass beide am Ende Geschenke mit demselben Gesamtwert bekommen. Dabei muss jedes Kind mindestens ein Geschenk bekommen, Geschenke durfen nicht doppelt vergeben werden, der Nikolaus darf aber auch einige Geschenke fur sich behalten. Zeigen Sie, dass der Nikolaus stets eine Losung nden kann. ich komm einfach nicht drauf wie man das zeigen soll.... Meine Ideen: wir wissen dass es mögliche Gesamtwert bis 64000 gibt Und dass es darum geht zu zeigen dass es immer zwei Teilmengen A und B von der Geschenkemenge gibt für die Gilt Wert(A) = Wert(B) und |A| + |B| < 17 und A geschnitten B = leere Menge. |
||
| 06.01.2014, 16:40 | Math1986 | Auf diesen Beitrag antworten » |
| RE: Schubfachprinzip Hallo, das vorgehen geht wie folgt: -Überlege dir, wie viele Teilmengen du aus den 16 Geschenken bilden kannst (ausgenommen der leeren Menge) -Überlege dir, welchen Gesamtwert eine solche Auswahl maximal haben kann (->Schubfächer) -Nimm an, die Aussage ist falsch, und führe dies zu einem Widerspruch. Nachtrag: Damit kann mann auf jeden Fall zeigen, dass man 2 Teilmengen mit dem selben Gesamtwert finden kann, wegen der Disjunktheit müsste man sich nochmal Gedanken machen, sollte aber auch irgendwie so ähnlich funktionieren. Nachtrag 2: Disjunktheit kann man wie folgt ausschließen: Angenommen, die oben gefundenen Mengen seien nicht disjunkt und haben den selben Wert. kann nicht passieren, da sonst die größere menge auch einen höheren Gesamtwert hat. Man konstruiere nun aus A und B zwei neue disjunkte Mengen , die den selben Gesamtwert haben. |
||
| 06.01.2014, 22:41 | ter11 | Auf diesen Beitrag antworten » |
| RE: Schubfachprinzip danke !! hat mir sehr geholfen |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
