Neue Aufgaben Nr. 2 < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 19:48 Mo 14.02.2005 | | Autor: | Hanno |
Hallo an alle!
Hier wie angekündigt die zweite Aufgabe:
Sei $p>2$ eine Primzahl. Wie viele Teilmengen der Menge [mm] $\{1,2,...,2p\}$ [/mm] gibt es, für die die Summe ihrer Elemente durch $p$ teilbar ist?
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:34 Fr 18.02.2005 | | Autor: | Max |
Hallo Hanno,
hier meine Lösung zu dieser netten Aufgabe.
Behauptung: Es gibt zu jeder Primzahl $p>2$ genau $4$ Teilmengen, für die gilt, dass die Summe ihrer Elemente durch $p$ teilbar ist.
Beweis:
Für eine Teilmenge [mm] $\{1; 2; \ldots; k\} \subseteq \{1; 2; \ldots; 2p\}$ [/mm] ist die Summe der Elemete der Teilmenge [mm] $s(k)=\frac{k(k+1)}{2}$.
[/mm]
Es gilt:
$p | s(k) [mm] \gdw [/mm] p | k(k+1) [mm] \gdw \left( p | k \vee p|k+1\right) [/mm] $
Die einzigen Möglichkeiten dass $p|k$ sind $k=p$ und $k=2p$. Die einzige Möglichkeit dass $p|k+1$ sind $k=p-1$ und $k=2p-1$. [mm] \Box
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:25 Sa 19.02.2005 | | Autor: | Hanno |
Hallo Max!
Deine Ausführungen sind zwar korrekt, doch sie Beschränken das Problem auf einen relativ einfachen Fall; du betrachtest lediglich Teilmengen der Form [mm] $\{1,2,...,k\}$, [/mm] nicht aber beliebige Teilmengen der Menge [mm] $\{1,2,...,2p\}$. [/mm] Auf andere Teilmengen als die von dir behandelten sind deine weiteren Ausführungen nicht anzuwenden.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:38 Sa 19.02.2005 | | Autor: | Max |
Naja, dass hätte ich ja mal alleine wissen können - ich sollte mich nicht mehr Nachts an sowas setzten  Mal sehen, ob ich das dann auch für beliebige Teilmengen hinbekomme...
Max
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:32 So 20.02.2005 | | Autor: | Max |
Hi Hanno,
kann ich nicht alle Teilmengen aus den angegebenen Mengen
[mm] $M_{p-1}=\{1; 2; \ldots; p-1\}$
[/mm]
[mm] $M_{p}=\{1; 2; \ldots; p\}$
[/mm]
[mm] $M_{2p-1}=\{1; 2; \ldots; 2p-1\}$
[/mm]
[mm] $M_{2p}=\{1; 2; \ldots; 2p\}$
[/mm]
erzeugen?
Wenn ich entsprechende Differenzmengen bilde, komme ich nach und nach zu allen möglichen Mengen, deren Summe der Elemente durch $p$ teilbar ist, da sich diese Eigenschaft auf Differenzmengen überträgt. Vereinigt man Mengen - deren Schnittmenge leer ist - überträgt sich diese Eigenschaft auch. Ich muss jetzt nur noch in einer ruhigen Minute mal nachdenken, wie ich geschickt alle Möglichkeiten herausfinden kann...
Max
|
|
|
| |
|
Hi Max,
deine Antwort kann ich so nicht nachvollziehen. Sei p=5, d.h. M={1,2,...,10}.
Wie willst du mit deinem Verfahren der Differenzbildung z.B. die Menge {1,4,5}, deren Summe ein Vielfaches von 5 ist, abdecken?
Liebe Grüße,
Andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:28 Mi 05.10.2005 | | Autor: | ZetaX |
Hallo Hanno!
Im Folgenden möge alles, was nicht Anzahlen betrifft, im Ring [mm] $\mathbb{Z} [/mm] / p [mm] \mathbb{Z}$ [/mm] bzw. nachher in [mm] $\mathbb{Z} [/mm] / (kp) [mm] \mathbb{Z}$ [/mm] geschehen, insbesondere sei ein [mm] $\mod [/mm] p$ bzw. [mm] $\mod [/mm] kp$ immer weggelassen.
Für eine Menge von ganzen Zahlen bzw. Restklassen bezeichne [mm] $\sigma(T)$ [/mm] ihre Elementsumme.
Zuerst einmal zu einem leichteren Problem:
Sei ein ganzzahliges $a$ und eine Primzahl $p$ gegeben.
Wieviele Teilmengen der Menge [mm] $P=\{ 1,2,3,...,p \}$ [/mm] gibt es, so dass deren Elementsumme gleich/kongruent $a$ ist¿
Antwort:
[mm] $f(n)=\begin{cases} \frac{2^p-2}{p}+2, & \mbox{für } p|a \\ \frac{2^p-2}{p}, & \mbox{sonst}\end{cases}$
[/mm]
Beweis:
Die beiden 'trivialen' Mengen, die leere Menge und ihr Komplement, erfüllen die Bedingung genau dann wenn $p|a$. Diese liefern dann auch das $+2$ in der Fallunterscheidung.
Nun hat man zu einer nichttrivialen Teilmenge $T$ immer $p$ 'translatierte' Teilmengen $x+T := [mm] \{ x+t | t \in T \}$ [/mm] wobei $x [mm] \in \mathbb{Z} [/mm] / p [mm] \mathbb{Z}$. [/mm] Diese sind tatsächlich alle verschieden:
Da $T$ nichttrivial ist, gibt es ein $t [mm] \in [/mm] T$. Wäre nun $T=x+T$, so sind auch $x+r,2x+t,3x+t,...,(p-1)x+t,px+t=t$ in $T$ enthalten, aber für $x [mm] \neq [/mm] 0$ auch alle verschieden. Also ist $T$ doch trivial, Widerspruch.
Wäre nun $x+T=y+T$, so folgt sofort $(x-y)+T=T$, also $x=y$.
Besitzt nun aber $T$ die Elementsumme [mm] $\sigma [/mm] (T)$, so ist [mm] $\sigma (x+T)=\sigma (T)+x\cdot [/mm] |T|$. Dann sind aber (da $p [mm] \nmid [/mm] |T|$) die Elementsummen der verschiedenen Translatierten von $T$ alle verschieden, insbesondere ist genau eine gleich $a$.
Unterteil man nun die Menge aller [mm] $2^p-2$ [/mm] nichtrivialen Teilmengen in Translations-Klassen, so enthält also jede genau eine Teilmenge der geforderten Art, also gibt es genau [mm] $\frac{2^p-2}{p}$ [/mm] davon.
Das ist aber schon die Behauptung.
Nun zur allgemeineren Frage:
Sei ein ganzzahliges $a$, eine Primzahl $p$ und ein natürliches $k$ gegeben.
Wieviele Teilmengen der Menge [mm] $P=\{ 1,2,3,...,kp \}$ [/mm] gibt es, so dass deren Elementsumme gleich/kongruent $a$ ist¿
Antwort:
[mm] $f(n)=\begin{cases} \frac{2^{kp}-2^k}{p}+2^k, & \mbox{für } p|a \\ \frac{2^{kp}-2^k}{p}, & \mbox{sonst}\end{cases}$
[/mm]
Beweis:
Wir unterteilen $P$ in $k$ Teilmengen [mm] $P_1=\{1,k+1,2k+1,...,(p-1)k+1\}; P_2=\{2,k+2,2k+2,...,(p-1)k+2\};...;P_k=\{k,2k,3k,...,pk\}$, [/mm] eben nach ihren Resten [mm] $\mod [/mm] k$. Weiter soll zu einer Teilmenge $T$ von $P$ im folgenden immer [mm] $T_i [/mm] := T [mm] \cap P_i$.
[/mm]
Nun nennen wir die Teilmenge $T$ trivial, wenn jedes [mm] $T_i$ [/mm] die leere Menge oder [mm] $=P_i$ [/mm] ist. Es gibt also [mm] $2^k$ [/mm] triviale Mengen.
Da die trivialen Mengen alle Summe $0$ haben, ergibt sich wie zuvor durch sie das [mm] $+2^k$ [/mm] in der Fallunterscheidung.
Das um $x$ Translatierte des von nun an nichttrivialen $T$, dieses mal geschrieben $x§T$, definieren wir nun folgendermaßen:
Ist $i$ minimal, so dass [mm] $T_i$ [/mm] selbst nichtrivial ist (also weder leer noch gleich [mm] $P_i$), [/mm] so definiert man $x§T := (T [mm] \backslash T_i) \cup (x\cdot k+T_i)$, [/mm] wobei [mm] $x+T_i$ [/mm] wie zuvor definiert sei.
Mit anderen Worten: man lässt alle Elemente gleich, nur diejenigen in [mm] $T_i$ [/mm] verschiebt man um [mm] $x\cdot [/mm] k$ (bzw. auf ihren 'Nachbarn' in [mm] $T_i$).
[/mm]
Nun gibt es wieder $p$ Translatierte, die alle verschieden sind (Beweis: analog wie zuvor).
Auch analog gibt es dann wieder genau ein translatiertes $T'$ mit [mm] $\sigma(T')=a$.
[/mm]
Somit ergibt sich die Anzahlformel auch wie zuvor.
q.e.d.
Es gibt auch eine Lösung für nicht notwendig primes $p$, welche aber etwas umständlicher/weniger schön ist (und noch dazu recht ähnlich zu beweisen). Ich stelle es mal hier als weitere Aufgabe, sie zu finden und nachzuweisen (Tip: es kommt die eulersche Phi-Funktion vor).
Auch kann man das ganze noch auf Teilmengen mit bestimmter Mächtigkeit einschränken, wobei sich dann an den Beweisen nicht viel ändert.
Grüße,
Daniel
|
|
|
|
![[respekt]](/images/smileys/respekt.gif "[respekt]"){kind=small}
![[applaus]](/images/smileys/applaus.gif "[applaus]"){kind=small}
