Schubfachprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:40 Sa 10.11.2012 | | Autor: | Lu- |
| Aufgabe | Zeige: Sei f : [k] -> [n] mit k>n, dann gibt es ein Element m [mm] \in [/mm] [n], für das gilt:
| [mm] f^{-1} [/mm] (m) | [mm] \ge \lfloor \frac{k-1}{n} \rfloor [/mm] +1
wobei [k] := [mm] \{1,..,k \}
[/mm]
[0]:= [mm] \{\} [/mm] |
Ich habe nur im Internet einen beweis dazu gefunden.
Angenommen [mm] \forall [/mm] m [mm] \in [/mm] [n] : [mm] |f^{-1} [/mm] (m)| < [mm] \lfloor \frac{k-1}{n} \rfloor [/mm] +1
<=> [mm] |f^{-1} [/mm] (m)| <= [mm] \lfloor \frac{k-1}{n} \rfloor
[/mm]
k= | [mm] f^{-1} [/mm] (1)| [mm] +|f^{-1} (2)|...+|f^{-1} [/mm] (n)|
k= [mm] \sum_{n=1}^n [/mm] | [mm] f^{-1} [/mm] (m) | [mm] \le \sum_{n=1}^n \lfloor \frac{k-1}{n} \rfloor \le \sum_{n=1}^n \frac{k-1}{n} [/mm] = k-1
Wid.
Mir ist bei dem Beweis nur nicht klar: k= | [mm] f^{-1} [/mm] (1)| [mm] +...+|f^{-1} [/mm] (n)|
Vlt. trivial aber mir mag das nicht einleuchten...
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:45 Sa 10.11.2012 | | Autor: | Teufel |
Hi!
[mm] |f^{-1}(n)| [/mm] zählt ja die Anzahl der Urbilder von n, also die Anzahl aller [mm] k_n, [/mm] die auf n geworfen werden. Nun gilt, dass jedes [mm] $k_i \in [/mm] [k]$ auf irgendein [mm] $n_j \in [/mm] [n]$ geworfen wird. Daher müssen sich die Anzahlen aller Urbilder ja wieder zu k summieren (denn sonst hätte ein [mm] k_i [/mm] kein Bild, was aber nicht sein kann).
Oder vielleicht anders: Es gilt [mm] f^{-1}(1) \cup [/mm] ... [mm] \cup f^{-1}(n) [/mm] = [mm] f^{-1}([n])=[k]. [/mm] Daher folgt [mm] k=|[k]|=|f^{-1}(1) \cup [/mm] ... [mm] \cup f^{-1}(n)|=|f^{-1}(1)|+ ...+|f^{-1}(n)| [/mm] (da die Urbildmengen alle disjunkt sind).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:57 Sa 10.11.2012 | | Autor: | Lu- |
danke für die erklärung.
lg
|
|
|
|
