p ist eine ungerade Primzahl. Wieviele Teilmengen von A = {1, 2, … , 2p} gibt es, deren Summen ihrer Elemente durch p teilbar ist.
Observations (keine Lsg.)
Hallo,
den Rest (wenn das hier keine Sackgasse ist) muß ich mir heute abend oder morgen anschauen, wenn ich wieder Zeit dazu habe.
Sei Sp={T | p teilt sumi Element T i und T Teilmenge von [1,2p]) die Menge der Lsg. Es gilt also die Maechtigkeit von Sp zu bestimmen. Wg. sum1 i=(2p+1)p kommen dafuer genau die Summen mit Ergebnis 0p,1p,…,(2p+1)p in Betracht, also insgesamt 2p+2. Sei Lk={T | sumi Element T i=kp und T Teilmenge von [1,2p]). Dann gilt:
Sp=L0 + L1 + L2 + … + L2p+1 (+: (disjunkte) Vereinigung)
Das Problem ist symmetrisch, es gilt #Lk=#L2p+1-k, da fuer jedes T aus Lk, [1,2p]-T in L2p+1-k liegt (-: Mengendifferenz). Denn sei sumi Element T i=kp. Dann gilt:
sumi Element [1,2p]-T i=(2p+1)*p-sumi Element T i=(2k+1-k)*p
Also reicht es L0,L1,…,Lp zu betrachten (man weiss jetzt auch schon, dass die Anzahl der gesuchten Teilmengen gerade ist).
L0={{}}, also #L0=1, da jedes nichtleere T aus [1,2p] eine Summe groesser 0 ergeben wuerde (aus der Symmetrie folgt damit L2p+1={[1,2p]} und #L2p+1=1).
Umgekehrt könnte man die Lsg. statt sie nach der Summe zu klassifizieren, nach ihre Mächtigkeit (Mengen mit 0,1,2,…,2p Elementen) unterscheiden. Sei
Mn={T | T Element von Sp und #T=n}
Dann gilt wieder
Sp=M0 + M1 + … + M2p
und aus obiger Symmetrie-Betrachtung folgt auch das #Mn=#M2p-n.
Mal sehen ob ich da nachher noch weiter komme …
Gruss
Enno
Nachfrage
Hallo,
welche Form von Lsg. wird hier erwartet ? „Reicht“ eine rekursiv definierte Zahlenfolge oder ist eine geschlossene Darstellung gesucht ?
Gruss
Enno
„Reicht“ eine rekursiv definierte Zahlenfolge oder ist
eine geschlossene Darstellung gesucht ?
geschlossene Darstellung
Ok
Hallo,
die entscheidende Entdeckung habe ich vermutlich gerade gemacht. Vermutlich ist #Mn=binom(2p,n)/p (für 0n siehe anderes Posting). Warum und ob dem so ist, ist noch abzuklären.
Gruss
Enno