Hallo,
ich habe mir heute noch mal das Rätsel
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…
angeschaut. Die Frage war, wieviel Teilmengen von {1,2,…,2p} es gibt, die durch p teilbar sind, wobei p>2 eine Primzahl ist. Klassifiziert man diese Teilmengen nach der Anzahl ihrer Elemente
Lk={ T | T ist eine k-elementige Teilmenge von [1,2p] und p teilt sumi Element T i }
ergibt sich die Gesamtlösungsmenge als disjunkte Vereinigung aller Lk und somit die gesuchte Anzahl als Summe der Anzahl der Elemente der einzelnen Lk.
Nun zeigt man leicht, daß #Lk=#L2p-k, denn die Summe 1+2+…+2p ist durch p teilbar und man erhält zu jeder Lsg. einer k-elementigen Teilmenge genau eine 2p-k elementige Teilmenge, die ebenfalls durch p teilbar ist, durch Komplementbildung (bzgl. [1,2p]). Damit läßt sich das Problem zerlegen in die Bestimmung von:
-
#L0
Nun hier gibt es offensichtlich genau eine Lsg., nämlich die leere Menge, also gilt #L0=1. - #Lk für 0k=1/p*binom(2p,k) ergibt.
-
#Lp (m.M. der schwerste Fall, sonst wäre die Lsg. bereits nach 2 Tagen dagewesen - so habe ich den Kram erst mal „geparkt“)
In ähnlicher Weise kann man zeigen, daß für diesen die p-elementigen Teilmengen, deren Summe nicht durch p teilbar ist, alle die Mächtigkeit 1/p*(binom(2p,p)-2) haben. Damit ergibt sich #Lp=1/p*(binom(2p,p)-2)+2.
Summiert man nun alles zusammen erhält man 4+1/p*(22p-4) bzw. 1/p*(22p+4(p-1)).
Gruss
Enno
)