Schubfachprinzip |
| 09.01.2016, 01:07 | Mr. Lego | Auf diesen Beitrag antworten » | ||
| Schubfachprinzip Wir haben folgende Aufgabe gestellt bekommen: Sei A eine k-elementige Teilmenge von {1,2,...,N} wobei k>2*N^(1/2)+1. Zeigen Sie, dass in A zwei unterschiedliche Paare (a1,b1) und (a2,b2) existieren sodass a1<b2 und a2<b2 ist und a1+b1=a2+b2 ist. Leider weiß ich nicht wirklich wie ich da vorgehen soll... Mein Ansatz wäre die Möglichkeiten aller Summen mit der Partitionsfunktion zu berechnen und dann mit dem Schubfachprinzip zu argumentieren, dass solche Paare existieren. Nur fehlt mir die Fähigkeit dies umzusetzen bzw weiß ich auch nicht ob, dass stimmt. Ich hoffe ihr könnt mir bei meinem Problem helfen. |
||||
| 09.01.2016, 02:08 | HAL 9000 | Auf diesen Beitrag antworten » | ||
In welchem Intervall bewegen sich denn die möglichen Summenwerte von Paaren mit ? |
||||
| 09.01.2016, 13:54 | Mr. Lego | Auf diesen Beitrag antworten » | ||
Naja, eigentlich zwischen 2 und 2N, da (1,1) und (N,N) auch Paare sind. Wegen der Angabe fallen aber 2 und 3 als mögliche Summenwerte weg, da bei 2 beide Paare gleich sind ((1,1)=(1,1)) und bei 3 entweder a1<b2 oder a2<b2 nicht erfüllt ist. D.h. der tatsächliche kleinste Wert ist 4, da a1=b1=2 und a2=1 und b2=3 alle Bedingungen erfüllen. Bei dem größten Wert läufts ähnlich, 2*N und 2*N-1 fallen weg, aber 2*N-2 ist möglich wegen (N-2,N) und (N-1,N-1). Also liegen meine Summenwerte im Intervall von 4 bis 2*N-2. Inwiefern hilft mir das der Lösung näher zukommen? Irgendwie steh ich gerade Zürich auf der Leitung... |
||||
| 09.01.2016, 15:04 | HAL 9000 | Auf diesen Beitrag antworten » | ||
fällt nicht weg. Dafür ist aber nicht möglich, sondern maximal . Wir reden hier wohlgemerkt nur über ein Paar - du scheinst das schon mit der Frage nach zwei Paaren zu vermengen, davon ist noch keine Rede. 
Ok, von bis sind es insgesamt mögliche Werte für die Summe. Weiter: Wieviel verschiedene Paare mit sowie gibt es denn? |
||||
| 09.01.2016, 16:34 | Mr.Lego | Auf diesen Beitrag antworten » | ||
Ah OK, dann hab ich das etwas falsch verstanden, aber danke schonmal. Also dann haben wir 2N-3 Möglichkeiten für die Summe. Die Anzahl der Möglichkeiten von den Paaren (a,b) aus A würde ich so berechnen: Für a=1 darf b zwischen 2 und N sein, also N-1 Möglichkeiten. Für a=2 darf b zwischen 3 und N sein, also N-2 Möglichkeiten. ... Für a=N-1 darf b nur N sein. Also 1 Möglichkeit. D. h. es gibt 1+2+...+(N-2)+(N-1) Möglichkeiten. Was mit kleinen Gauß (N-1)*N\2 ergibt. Allerdings steh ich immer noch auf dem Schlauch 
Also wie soll ich weiter vorgehen? |
||||
| 09.01.2016, 16:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Die Menge A enthält nicht N, sondern nur k Elemente. Das bedeutet, es gibt solche Paare. Falls nun ist, dann gilt nach Schubfachprinzip... |
||||
| Anzeige | ||||
|
|
||||
| 09.01.2016, 18:08 | Mr. Lego | Auf diesen Beitrag antworten » | ||
Ah jetzt ergibt es Sinn, d.h. ich kann dann sagen: k*(k-1)/2 > (2N^(1/2)+1)*2N^(1/2)/2=(4N+2N^(1/2))/2=2N+N^(1/2) und das ist auf jeden Fall größer als 2N-3. Also folgt nach Schubfachprinzip dass es mindestens 2 unterschiedliche Paare (a,b) mit a<b gibt, die dieselbe Summe haben. Und dass a1<b2 ist folgt ja sowieso, da a1<b1 und a2<b2... Stimmt das so? Auf jeden Fall danke, du hast mir bereits sehr geholfen. |
||||
| 09.01.2016, 18:13 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ja, das ist es schon alles. 
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
