Taubenschlagprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:00 Fr 06.04.2007 | | Autor: | bobie |
n Tauben verteilen sich auf k Taubenschläge, wobei Mehrfachbelegungen möglich sind. Zu zeigen ist, dass es Taubenschläge gibt, in denen sich min. n/k bzw. höchstens n/k Tauben befinden.
Kann mir jemand bei dieser Aufgabe helfen?
Als Info ist noch angegeben: x=min {n aus Z: n>=x}
x=max {n aus Z: n<=x}
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:38 Fr 06.04.2007 | | Autor: | felixf |
Hallo bobie!
> n Tauben verteilen sich auf k Taubenschläge, wobei
> Mehrfachbelegungen möglich sind. Zu zeigen ist, dass es
> Taubenschläge gibt, in denen sich min. n/k bzw. höchstens
> n/k Tauben befinden.
> Kann mir jemand bei dieser Aufgabe helfen?
> Als Info ist noch angegeben: x=min {n aus Z: n>=x}
> x=max {n aus Z: n<=x}
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Du hast hier ein paar Zeichen wie [mm] $\lfloor \; \rfloor$ [/mm] und [mm] $\lceil \; \rceil$ [/mm] weggelassen, nicht?
Zur generellen Idee: Nimm doch mal an, in allen Taubenschlaegen sind echt weniger als $n/k$ Tauben. Dann gibt es insgesamt weniger als $k [mm] \cdot [/mm] n/k = n$ Tauben, ein Widerspruch. Also muss es in einem Taubenschlag mindestens $n/k$ Tauben geben.
Fuer das andere geht es genauso.
Und wie du dann das Runden mit reinbekommst musst du dir selber ueberlegen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:07 So 08.04.2007 | | Autor: | bobie |
Danke erstmal, aber ich verstehe das noch nicht so ganz!
Warum k x n/k = n? Was beschreibt das genau?
|
|
|
| |
|
Hallo bobie!
> Danke erstmal, aber ich verstehe das noch nicht so ganz!
> Warum k x n/k = n? Was beschreibt das genau?
Wenn du das Gegenteil annimmst, also dass in allen Taubenschlägen weniger als [mm] \frac{n}{k} [/mm] Tauben sind, dann hättest du insgesamt (da ja k Taubenschläge) weniger als [mm] k*\frac{n}{k}=n [/mm] Tauben. Da es aber n Tauben waren, hast du einen Widerspruch. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
