Aufgabe #50 (IrMO) < MO andere Länder < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 10:48 Sa 09.07.2005 | | Autor: | Hanno |
Hallo an alle!
Es seien $p$ eine ungerade Primzahl und $n$ eine natürliche Zahl, ferner [mm] $T=\{1,2,...,n\}$. [/mm] Wir nennen $n$ p-partitionierbar, wenn eine Partition von $T$ in $p$ nichtleere, disjunkte Teilmengen [mm] $T_1,T_2,...,T_p$ [/mm] existert, für die die Summe der Elemente in den [mm] $T_i$ [/mm] gleich ist.
(a) Es sei $n$ p-partitionierbar. Beweise, dass $p$ ein Teiler von $n$ oder $n+1$ ist.
(b) Es sei $n$ durch $2p$ teilbar. Beweise, dass $n$ p-partitionierbar.
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:40 Sa 09.07.2005 | | Autor: | DaMenge |
Hallo,
kann es sein, dass hier etwas fehlt?
für $ [mm] p\le [/mm] n $ ist n doch immer p-partionierbar durch:
$ [mm] T_i =\{ i \} [/mm] $ (für alle i < p ) und $ [mm] T_p [/mm] = [mm] \{ p, p+1 ,..., n \} [/mm] $
Die Partitionen haben die gewünschten eigenschaften,
also ist 7 3-partitionierbar, aber weder 7 noch 8 haben den Teiler 3.
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Sa 09.07.2005 | | Autor: | Hanno |
Hallo!
Du hast natürlich recht ;) Die wichtigste Information hatte ich ausgelassen. Ich hab's nun korrigiert.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:46 So 10.07.2005 | | Autor: | moudi |
Hallo Hanno
Diese Aufgabe scheint mir nicht so schwierig.
a) Die Summe aller Zahlen in T ist [mm] $1+2+\dots+n=\frac{n(n+1)}{2}$.
[/mm]
Wenn n p-partitionierbar ist, und die Summe aller Zahlen in einer Teilmenge der Partition gleich s ist, dann muss [mm] $ps=\frac{n(n+1)}{2}$ [/mm] gelten. Da p eine Primzahl ist, muss dann p ein Teiler von n oder n+1 sein.
b) Wenn n gerade ist, dann kann man die [mm] $\frac [/mm] n2$ Paarmengen
[mm] $\{1,n\},\{2,n-1\},\dots\{\frac{n}{2},\frac{n}{2}+1\}$ [/mm] bilden, deren Summen der Elemente gleich sind.
Wenn [mm] $\frac{n}{2}$ [/mm] noch durch p teilbar ist, etwa [mm] $k\cdot p=\frac{n}{2}$, [/mm] dann kann man je k der Paarmengen zu einer Menge vereinigen und man erhält so eine Partition von [mm] $\{1,\dots,n\}$ [/mm] in p Teilmengen, deren Elementsummen alle gleich sind.
mfG Moudi
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:00 So 10.07.2005 | | Autor: | Hanno |
Hallo moudi!
Ja, wunderbar! Es muss auch mal leichtere Aufgaben zwischendurch geben :)
Liebe Grüße,
Hanno
|
|
|
|
