Aufgabe #60, IMO2005, #6 < Internationale MO < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 20:30 Sa 16.07.2005 | | Autor: | Hanno |
Hallo an alle!
In einem Mathematikwettbewerb waren 6 Aufgaben zu lösen. Je zwei von ihnen wurden von mehr als [mm] $\frac{2}{5}$ [/mm] der Teilnehmer gelöst. Ferner löste kein Teilnehmer alle 6 Probleme. Man beweise, dass es wenigstens zwei Teilnehmer gab, die jeder genau 5 der 6 Aufgaben lösten.
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:34 Sa 16.07.2005 | | Autor: | jbulling |
Hallo Hanno,
hier mal mein Versuch:
n = Anzahl der Teilnehmer
Ich nehme an, dass n>=2 gilt :o)
Anzahl Aufgabenpaare insgesamt [mm] \bruch{6*5}{2}=15
[/mm]
davon darf jeder Teilnehmer maximal [mm] \bruch{5*4}{2}=10 [/mm] lösen! (keiner löst 6 Aufgaben)
[mm] \bruch{5*4}{2}=10 [/mm] deswegen, weil aus 5 gelösten Aufgaben genau 10 Paare gebildet werden können, wenn man die Reihenfolge nicht betrachtet (es ist ja egal, ob ein Teilnehmer die Aufgabe 3 und 5 oder 5 und 3 bearbeitet hat). Der Bruch ist also eigentlich 5 über 2, so wie auch der Bruch [mm] \bruch{6*5}{2}=15 [/mm] als 6 über 2 zu verstehen ist.
x=Anzahl gelöster Aufgabenpaare gesamt
x >= 15 * (n+1) * [mm] \bruch{2}{5} [/mm] = 6 * (n+1) = 6n + 6
Denn jedes der 15 möglichen Paare wurde von mindestens [mm] (n+1)*\bruch{2}{5} [/mm] Teilnehmern gelöst.
Wenn jeder 4 Aufgaben lösen würde, dann wären das
n * [mm] \bruch{4*3}{2} [/mm] = n * 6
Es reicht also nicht aus, wenn nur einer der Teilnehmer 5 Aufgaben löst, denn es gilt:
5 Aufgaben sind 10 Paare (siehe oben)
4 Aufgaben sind 6 Paare (siehe oben)
es gilt also
(n-1)*6 + 10 = 6n + 4 < 6n + 6 < (n-2)*6 + 2*10 = 6n + 8
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:33 Sa 16.07.2005 | | Autor: | Hanno |
Hallo Jürgen!
> x >= 15 * (n+1) * $ [mm] \bruch{2}{5} [/mm] $ = 6 * (n+1) = 6n + 6
> Denn jedes der 15 möglichen Paare wurde von mindestens $ [mm] (n+1)\cdot{}\bruch{2}{5} [/mm] $ Teilnehmern gelöst.
Hier steckt leider ein Fehler. Vor der Multiplikation mit [mm] $15=\vektor{6\\ 2}$ [/mm] musst du den Wert von [mm] $(n+1)\cdot{}\bruch{2}{5}$ [/mm] aufrunden. Ansonsten passiert es, dass du ein zu großes Minimum erhältst und dies fälschlicher weise in einen Widerspruch führt.
Du musst hier ein wenig genauer werden. Der Ansatz ist aber der richtige.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:31 So 17.07.2005 | | Autor: | jbulling |
Hi Hanno,
danke für den Hinweis. Ich hatte vergessen, dass auch Mathematiker unteilbar sind :o)
Um das noch miteinzubeziehen müsste man einfach n in der Form n=5m + r mit m [mm] \in \IN [/mm] und 0 <= r < 5 schreiben.
Dann kann man das Ganze mit Fallunterscheidungen lösen.
Im Fall 1: r=0 sieht die Lösung wie vorher beschrieben aus.
Im Fall 2: 1 => r > 0
x >= 15 * (n + 1) * [mm] \bruch{2}{5} [/mm] = 15 * (5m + r + 1) * [mm] \bruch{2}{5} [/mm] >= 15 * (2m+1) = 30m + 15
Wenn jeder davon 4 Aufgaben lösen würde:
n * 4*3/2 = 6(5m + r) = 30m + 6r
wobei wegen 0 <= r <= 1 gilt:
0 <= 6r <= 6
Wie im Artikel vorher argumentiert werden pro Teilnehmer, der 5 statt 4 Aufgaben löstm genau 4 Aufgabenpaare mehr abgedeckt. Somit müssen in diesem Fall sogar mindestens 3 Teilnehmer 5 Aufgaben lösen, um die Differenz von 9 Paaren abzudecken.
Fall 3: 5 > r > 1 (2 <= r <= 4)
x >= 15 * (n + 1) * [mm] \bruch{2}{5} [/mm] = 15 * (5m + r + 1) * [mm] \bruch{2}{5} [/mm] >= 15 * (5(m+1)) * [mm] \bruch{2}{5} [/mm] = 15 * 2(m+1) = 30m + 30
Wenn jeder davon 4 Aufgaben lösen würde:
n * 4*3/2 = 6(5m + r) = 30m + 6r
wobei wegen 1 < r <= 4 gilt:
12 <= 6r <= 24
Es bleibt also auch in diesem Fall eine Differenz von mindestens 6 Aufgabenpaaren. Da aber nur 6 Aufgabenpaare mehr abgedeckt werden, wenn ein Teilnehmer statt 4 Aufgaben 5 löst, müssen auch in diesem Fall mindestens 2 Teilnehmer 5 Aufgaben lösen.
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:59 So 17.07.2005 | | Autor: | Hanno |
Hallo Jürgen!
Leider steckt noch immer ein Fehler in deinen Ausführungen. Die Formel [mm] $\lceil\frac{2(n+1)}{5}\rceil$ [/mm] für die Mindestanzahl der Lösungen für je zwei Aufgaben ist nicht korrekt (es tut mir leid, dass ich dies in der ersten Antwort schrieb - es stimmt nicht). Sie ist nämlich genau dann falsch, wenn n den Rest 2 bei Division durch 5 lässt. Beispiel 7: über obige Formel erhältst du 4 als Mindestanzahl, nach der Aufgabenstellung müssten es aber 3 sein. In den anderen Fällen scheint mir das Ganze zu funktionieren. Im Sonderfall [mm] $n\equiv 2\pmod [/mm] {5}$ kannst du diese Formel jedoch nicht anwenden.
Ansonsten ist es richtig. Dieser verbleibende Sonderfall allerdings wird sich, wie du merken wirst, als nicht so leicht abzutun herausstellen, wie man vielleicht hoffen könnte.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:47 So 17.07.2005 | | Autor: | jbulling |
Hi Hanno,
okay, ich glaube ich habe den Fehler. Es müssen [mm]15 * (\lfloor n * \bruch{2}{5} \rfloor + 1)[/mm] Paare abgedeckt werden, wenn jedes Paar von mehr als [mm]\bruch{2}{5}[/mm] der Teilnehmer abgedeckt werden soll. Denn es gilt für [mm]n=5m+r[/mm] mit [mm]m \in \IR[/mm] und [mm]0<=r<5[/mm]:
[mm]y=15 * (\lfloor n * \bruch{2}{5} \rfloor + 1) - 15 * n * \bruch{2}{5}[/mm] = [mm] \begin{cases} y=15, & \mbox{für } r=0 \\ 00 \end{cases}
[/mm]
Die mit [mm]15 * (\lfloor n * \bruch{2}{5} \rfloor + 1)[/mm] ermittelte Anzahl von Paaren entspricht somit der Zahl die man erhält, wenn jedes Aufgabenpaar mal mehr als von [mm]n*\frac{2}{5}[/mm] Teilnehmern beantwortet wurde. Denn es gilt:
[mm]\lfloor n*\frac{2}{5} \rfloor <= n*\frac{2}{5} <= \lfloor n*\frac{2}{5} \rfloor + 1[/mm]
Richtig müsste es also folgendermaßen sein:
Fall 1: [mm]r = 0[/mm]
[mm]x >= 15 * (\lfloor n * \bruch{2}{5} \rfloor + 1) = 15 * (\lfloor (5m + r) * \bruch{2}{5} \rfloor + 1) = 15 * (2m+1) = 30m + 15[/mm]
Wenn jeder davon 4 Aufgaben lösen würde:
[mm]n * \vektor{4 \\ 2} = 6n = 6(5m+r) = 30m + 6r = 30m[/mm]
Also gibt es im Fall r=0 eine Differenz von 15 Aufgabenpaaren. Es müssen demnach im Fall r=0 mindestens 3 Teilnehmer 5 Aufgaben lösen.
Fall 2: [mm]1 <= r < 2[/mm]
[mm]x >= 15 * (\lfloor n * \bruch{2}{5} \rfloor + 1) = 15 * (\lfloor (5m + r) * \bruch{2}{5} \rfloor + 1) = 15 * (2m + 1) = 30m + 15[/mm]
Es gilt nämlich wegen [mm]1 <= r <= 2[/mm], dass [mm]0 < 1*\frac{2}{5} <= r*\frac{2}{5} <= 2*\frac{2}{5} < 1[/mm]. Also [mm]\lfloor r*\frac{2}{5}\rfloor=0[/mm].
Wenn jeder davon 4 Aufgaben lösen würde:
[mm]n * \vektor{4 \\ 2} = 6n = 6(5m+r) = 30m + 6r[/mm]
Also gibt es im Fall r=1 eine Differenz von 9 Aufgabenpaaren. Es müssen demnach im Fall r=1 mindestens 2 Teilnehmer 5 Aufgaben lösen.
Der Fall r=2 muß gesondert betrachtet werden, wie Du geschrieben hast.
Fall 2: [mm]2 < r < 5[/mm] also [mm]3 <= r <= 4[/mm]
[mm]x >= 15 * (\lfloor n * \bruch{2}{5} \rfloor + 1) = 15 * (\lfloor (5m + r) * \bruch{2}{5} \rfloor + 1) = 15 * (2m+1 + 1) = 30m + 30[/mm]
Es gilt nämlich wegen [mm]3 <= r <= 4[/mm], dass [mm]1 < \frac{6}{5} <= r*\frac{2}{5} <= 4*\frac{2}{5} < 2[/mm]. Also [mm]\lfloor r*\frac{2}{3}\rfloor=1[/mm].
Wenn jeder davon 4 Aufgaben lösen würde:
[mm]n * \vektor{4 \\ 2} = 6n = 6(5m+r) = 30m + 6r[/mm]
Die Differenz ist also minimal 6 Aufgabenpaare und pro TN, der 5 statt 4 Aufgaben löst werden nur 4 zusätzliche Aufgabenpaare abgedeckt (5*4/2-4*3/2). Es müssen demnach mindestens 2 Teilnehmer 5 Aufgaben lösen.
Fall 3: r=2
Diesen Fall kann man abdecken, indem man die Zahl der Teilnehmer n modulo 15 betrachtet und dann nur die
Fall 3a: n [mm] \equiv [/mm] 2 (15)
Fall 3b: n [mm] \equiv [/mm] 7 (15)
Fall 3c: n [mm] \equiv [/mm] 12 (15)
betrachtet.
Das ist ziemlich mühselig. Ich habe das für Fall 3a mal gemacht.
Erst mal die eigentliche Idee dahinter: Wenn man die Zahl der Teilnehmer n darstellt als
[mm]n=15t+q[/mm] wobei gilt [mm]q,t \in \IN[/mm] mit [mm]0 <= t < 15[/mm]
dann erhält erreicht man für q=0 eine optimale Verteilung der Aufgabenpaare, indem man jeweils t-mal ein bestimmtes Paar wegläßt (6-2=4 Aufgaben). Dadurch kommt jedes Aufgabenpaar genau 6t-mal vor. Insgesamt somit 2/5n-mal.
Fall 3a (q=2) gilt somit:
Die Teilnehmer können so angeordnet werden, dass alle Aufgabenpaare unter den gelösten Aufgaben der ersten 15t Teilnehmer genau gleich oft vorkommen. Deshalb reicht es aus, wenn man zeigt, dass zwei Teilnehmern, von denen der eine 4 Aufgaben löst und der Andere 5 nicht alle 15 Aufgaben abgedeckt werden können.
Der Teilnehmer mit den 5 Aufgaben deckt 10 Aufgabenpaare ab. Der Teilnehmer mit den 4 Aufgaben deckt 6 Aufgabenpaare ab. Es gibt aber mindestens 3 Aufgaben, die beide Teilnehmer gelöst haben müssen, da es nur 6 Aufgaben gibt. Auf diese 3 Aufgaben entfallen somit 3 Aufgabenpaare, die von beiden Teilnehmern abgedeckt werden. Somit decken die beiden Teilnehmer nur maximal 13 der 15 Aufgaben ab.
Hinweis: ich bin mir bewusst, dass ich eigentlich zeigen müsste, dass ich annehmen darf, dass jede andere Anordnung, bei denen die Teilnehmer nicht so angeordnet werden können, dass die ersten 15t Teilnehmer alle Aufgabenpaare gleich oft abdecken, nicht zu einer Lösung führt. Das habe ich allerdings noch nicht geschafft :o(
Die beiden anderen Fälle 3b und 3c müsste man genauso zeigen können, wie 3a.
|
|
|
|
