Auswahlaufgabe zur IMO Nr 2. < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 16:34 Sa 25.12.2004 | | Autor: | Hanno |
Hallo an alle!
Weiter geht's mit folgender Aufgabe:
Sei [mm] $F:=\{A_1,A_2,...,A_n\}$ [/mm] eine Menge von Teilmengen der Menge [mm] $S=\{1,2,...,n\}$ [/mm] mit den folgenden Eigenschaften:
a.) Je zwei der Mengen aus $F$ haben genau ein Element aus $S$ gemein.
b.) Jedes Element aus $S$ ist in genau $k$ der n Mengen aus $F$ enthalten.
Ist dies für n=1996 möglich?
Liebe Grüße und Viel Spaß,
Hanno
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:10 Sa 25.12.2004 | | Autor: | Hanno |
Huhu!
Ich weiß nicht, ob die IMO-Kandidaten solche Formeln kennen müssen, aber ich hatte die Idee, hier von meiner Lieblingsformel, der Siebformel des Sylvester (auch als Prinzip der In- und Exklusion bekannt) Gebrauch zu machen. Die Formel lautet bekanntlich:
[mm] $\left\vert \bigcup_{i=1}^{n}{A_i}\right\vert=\summe_{r=1}^{n}{(-1)^{r-1}\cdot\summe_{L\subseteq \{1,2,...,n\}\atop |L|=r}\left\vert \bigcap_{l\in L}{A_l}\right\vert }$
[/mm]
Die linke Seite können wir für unser Beispiel zu $n$ vereinfachen. Wäre dem nämlich nicht so, dann gäbe es ein Element aus S, welches nicht keiner der n Mengen vorhanden wäre. Dann wäre allerdings $k=0$, die Mengen allesamt leer und somit könnten zwei beliebige Mengen nicht in genau einem Element übereinstimmen. Die linke Seite muss also gleich n sein.
Zur rechten Seite hatte ich mir folgendes überlegt:
Der Ausdruck [mm] $\summe_{L\subseteq \{1,2,...,n\}\atop |L|=r} \left\vert \bigcap_{l\in L} A_l\right\vert [/mm] $ kann zu [mm] $n\cdot\vektor{k\\ r}$ [/mm] vereinfacht werden. Dies liegt, so dachte ich, daran, dass es genau [mm] $\vektor{k\\ r}$ [/mm] r-elementige Teilmengen von F gibt, die r der k Mengen enthalten, die allesamt eines der Elemente aus S beinhalten. Nur dann ist nämlich die Kardinalität des Durchschnittes 1. Da es n verschiedene Elemente in S gibt, dachte ich also, dass die Summe zu [mm] $n\cdot\vektor{k\\ r}$ [/mm] vereinfacht werden könnte. Dies widerspricht aber dem Falle $r=2$, dann da zwei Mengen bekanntlich genau 1 ELement gemein haben, hat die Vereinigung immer die Kardinalität 1, die Summe hat also den Wert [mm] $\vektor{n\\ 2}$ [/mm] und nicht [mm] $n\cdot\vektor{k\\ 2}$, [/mm] wie in meiner vorangegangenen Überlegung.
Was ist da falsch bzw. was muss ich noch beachten?
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:17 So 26.12.2004 | | Autor: | Hanno |
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Huhu!!
Vielleicht ist meine Untersuchung des Termes $\summe_{L\subseteq \{1,2,...,n\}\atop |L|=2} \left \vert \bigcap_{l\in L} A_l \right\vert$ gar nicht so verkehrt! Denn wenn ich logisch begründen kann, warum er einerseits den Wert $\vektor{n\\ 2}$, andererseits aber auch $n\cdot\vektor{k\\2 }$ haben kann, dann folgt zusammen $\vektor{n\\ 2}=n\cdot\vektor{k\\2}\gdw n=k^2-k+1$.
Da 1996 aber nicht die Form $k^2-k+1$ hat, lässt sich keine Menge F mit den besagten Eigenschaften finden.
Was haltet ihr davon?
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:27 Fr 14.01.2005 | | Autor: | Hanno |
Huhu Stefan!
Danke für deine Antwort - das freut mich, dass die Lösung korrekt ist!
Allerdings war das wohl mehr Glück als Verstand. Ich habe eigentlich gedacht, ich könne meine heiß geliebte Siebformel anwenden und habe dann gemerkt, dass ich für den Fall n=2 Probleme bekomme - diese Probleme habe ich zuerst als Denkfehler interpretiert, bis ich dann darauf gekommen bin, dass daraus die notwendige Bedingung [mm] $\exists k\in \IN: n=k^2-k+1$ [/mm] folgt.
Aber naja, zum Ziel hat es geführt :)
Liebe Grüße,
Hanno
|
|
|
|
![[respekt]](/images/smileys/respekt.gif "[respekt]"){kind=small}
![[hut]](/images/smileys/hut.gif "[hut]"){kind=small}
