verzamelingen
Opgave - BrMO 2 1999 vraag 1
Voor ieder natuurlijk getal $n$ definiëren we $S_n$ als de verzameling bestaande uit de eerste $n$ natuurlijke getallen, dat is
$$S_n=\{1,2,3,4,\cdots,n-1,n\}.$$
(i) Voor welke waarde van $n$ is het mogelijk om $S_n$ uit te drukken als unie van twee niet-ledige verschillende deelverzamelingen zodat de elementen in de twee deelverzamelingen dezelfde som hebben?
(ii) Voor welke waarde van $n$ is het mogelijk om $S_n$ uit te drukken als unie van drie niet-ledige verschillende deelverzamelingen zodat de elementen in de drie deelverzamelingen dezelfde som hebben?
- login om te reageren
Oplossing
i)
$2|\frac{n(n+1)}{2}$ dus moet $n=4k$ of $n=4k-1$ met $k\neq 0$
ii)
$3|\frac{n(n+1)}{2}$ dus moet $n=3k$ of $n=3k-1$ met $k\neq 0,1$
Omdat de som van zo een verzameling steeds groter dan of gelijk is aan $n$, zijn de combinaties hierboven altijd mogelijk. Begin de verzamelingen te maken door steeds de grootste getallen eerst te plaatsen en dan aan te vullen tot de gewenste som, doe dit zo verder.
[ dit werkt voor geval i) duidelijk omdat $1$ set met de juiste som vormen voldoende is, aangezien de andere automatisch ook de helft als som zal hebben]
[ in geval ii) zou dit te eenvoudige stramien eventueel kunnen mislopen]
Opm.
Alternatief met expleciete constructies is mogelijk
i)
$n=4k$ $A=\{1,2 \cdots,k\} \cup \{3k+1 \cdots 4k\}$
en $B=\{k+1 \cdots 3k \}$.
$n=4k-1$:
$A=\{1,2 \cdots,k\} \cup \{3k+1 \cdots 4k-1\} \cup \{2k\}$
en $B=\{k+1 \cdots 3k \} \backslash \{2k\}$.
ii)
We bewijzen dit per inductie op het aantal $n$.
Oplossen voor $5,6,8,9$ is eenvoudig (basisstap) en dan aan iedere van de $3$ sets
voor oplossing van $x-1$, een vz. $x,x+5$, een vz $x+1,x+4$ en een verzameling $x+2,x+3$ toevoegen om het te bewijzen voor $x+5$