partities
Opgave - IrMO 1997 dag 3 vraag 4
Zij $p$ een oneven priemgetal. We zeggen dat $n$ voldoet aan $K_p$ als de verzameling $\{1,2,\ldots,n\}$ gepartitioneerd kan worden in $p$ disjuncte deelverzamelingen zodat de som van de elementen in iedere deelverzameling dezelfde is. Bijvoorbeeld, 5 voldoet aan $K_3$ omdat $\{1,2,3,4,5\}=\{1,4\}\cup\{2,3\}\cup\{5\}$. Toon aan dat als $n$ voldoet aan $K_p$, dan is $n$ of $n+1$ een veelvoud van $p$. Toon aan dat als $n$ een veelvoud is van $2p$, dan voldoet $n$ aan $K_p$.
- login om te reageren
Oplossing
a)Aangezien de verzameling wordt gesplitst in p verschillende deelverzamelingen met dezelfde waarde moet gelden dat de som van de elementen in de verzameling deelbaar is door p. M.a.w. $\frac{n(n+1)}{2p}=k$ of $p|n(n+1)$ en k is een natuurlijk getal.
Dus moet gelden dat $n$ of $n+1$ een veelvoud is van p.
b)Neem n gelijk aan 2pr met r een natuurlijk getal, dan geldt dat ieder van de $p$ deelverzamelingen een waarde moet hebben van $\frac{2pr(n+1)}{2p}=r(n+1)$.
Dit kan bereikt worden door steeds de $r$ kleinste en de $r$ grootste elementen bijeen te plaatsen van de overige elementen uit de oorspronkelijke set getallen. Er zijn dan $\frac{n}{2r}=p$ deelverzamelingen met gelijke waarde. En op die manier is aan de voorwaarde voldaan.
Dit komt dus overeen met $i,2pr+1-i$ samen te tellen en zo hebben we $pr$ koppels met de zelfde som $n+1$. Door nu in iedere verzameling $r$ verschillende koppels te steken, heeft iedere verzameling duidelijk dezelfde som.