matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathematik-WettbewerbeNeue Aufgaben Nr. 2
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Mathematik-Wettbewerbe" - Neue Aufgaben Nr. 2
Neue Aufgaben Nr. 2 < Wettbewerbe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Neue Aufgaben Nr. 2: Übungsaufgabe
Status: (Übungsaufgabe) Übungsaufgabe Status 
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

        
Bezug
Neue Aufgaben Nr. 2: Lösungsversuch
Status: (Frage) beantwortet Status 
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]

Bezug
                
Bezug
Neue Aufgaben Nr. 2: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                        
Bezug
Neue Aufgaben Nr. 2: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Neue Aufgaben Nr. 2: Neuer Versuch ;-)
Status: (Frage) beantwortet Status 
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








Bezug
                
Bezug
Neue Aufgaben Nr. 2: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:34 Mo 28.02.2005
Autor: Mathemagier

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

Bezug
        
Bezug
Neue Aufgaben Nr. 2: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                
Bezug
Neue Aufgaben Nr. 2: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:19 Do 27.10.2005
Autor: Stefan

Hallo Daniel!

Um die "Frage" ;-) mal in den beantworteten Zustand zu versetzen:

Ein mal wieder unglaublich geniale Lösung von dir, bei der ich (ebenfalls mal wieder) Probleme hatte sie überhaupt nachzuvollziehen, geschweige denn auch nur ansatzweise selber darauf gekommen wäre.

[respekt] [applaus]

Liebe Grüße
Stefan

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]