Urbildfunktion zu beweisen mit Schubfach-Prinzip

Question

Aufgabe:

Sei k ∈ N⁺ eine positive natürliche Zahl. Weiter seien A und B endliche Mengen mit

|A| > k |B|,
sowie eine Abbildung f : A → B . Zeigen Sie, dass ein b ∈ B existiert mit |f⁻¹ ({b})| ≥ k + 1.
Hier bezeichnet f⁻¹: P(B) → P(A) die Urbildfunktion von f

Problem/Ansatz:

Könnte jemand bei der Lösung helfen.

Ich weiß, dass sich die Aufgabe mit dem Schubfach-Prinzip lösen lässt aber ich weiß nicht, wie das gemacht wird.

Answer 1

Betrachte  alle  b ∈ B.

Diese b bilden also die Schubladen, auf die die Elemente

von A  verteilt werden sollen. Es kommen also in jede b-Schublade

die Elemente von A, die in der Urbildmenge  f⁻¹ ({b}) enthalten sind.

Da zu jedem b die Urbilder eindeutig bestimmt sind, ist damit für

jedes a∈A auch eindeutig eine Schublade bestimmt. Wären In jeder

Schublade höchstens k Elemente,  sind damit höchstens

|B|*k  Elemente verteilt.  Also gibt es mindestens ein b in

dessen Schublade mehr als k Elemente sind.

Comments

vielen vielen dank

könntest du mir bei einer anderen Aufgabe helfen selbst wenn es gegen Geld wäre?

https://www.mathelounge.de/644425/clutter-fur-x-eine-endliche-menge

das ist der Link der Frage.oder hier ist die Frage

ich bedanke mich im Voraus für deine Mühe.

---

Wie stimmt das Bild im Kommentar mit https://www.mathelounge.de/644425/clutter-fur-x-eine-endliche-menge überein?

---

asoo sorry aber keine Ahnung ich habe den Link kopiert und hier eingefügt aber irgendwie ist der Link falsch die andere Frage ist auch von mir aber ich meine diese Frage hier:

---

Mit Graphen und Blöcken kenne ich mich nicht so aus.

---

Graphen und Blöckefrage wurde in die Stacklounge verschoben. https://www.stacklounge.de/4773/chromatische-zahl-stochastik In theoretischer Informatik kennen sich die Spezialisten da wohl besser aus.