Benelux-set
Opgave - BxMO 2010 dag 1 vraag 1
Een eindige verzameling gehele getallen noemen we slecht als de som van zijn elementen
gelijk is aan $2010.$ Een eindige verzameling gehele getallen is een Benelux-verzameling als geen van zijn deelverzamelingen slecht is.
Bepaal het kleinste gehele getal $n $zodanig dat je de verzameling
$\{502, 503, 504, . . . , 2009\}$ kunt opdelen (partitioneren) in $n$ Benelux-verzamelingen.
(Een opdeling (partitie) van een verzameling $S$ in $n $deelverzamelingen is een collectie van $n$ paarsgewijs
disjuncte verzamelingen van $S,$ waarvan de vereniging (unie) gelijk is aan $S.)$
- login om te reageren
Oplossing
$n>1$, want anders zouden er bijvoorbeeld slechte deelverzamelingen als $\{1004,1006\} $ bestaan.
vanaf $n=2$ gaat het echter wel, bekijk de disjuncte deelverzamelingen
$A=\{502,503,\dots,670,1006,1007\dots1339,1509,1510,\dots,2009\}$
$B=\{671,672,\dots,1004,1005,1340,1341,\dots1508\}$
$A$ is een beneluxverzameling
Voor getallen van $502$ tot $670$ moet je respectievelijk $1508$ tot $1340$ optellen om $2010$ te bekomen, echter zitten deze laatste getallen niet in $A$. alle paren van 2 elementen van $A$ groter of gelijk aan $1006$ hebben een som groter dan $2010$ (minimum $502+503+1006=2011)$, dus we kunnen stellen dat $A$ geen slechte deelverzamelingen van 2 elementen heeft. A heeft trouwens ook geen slechte deelverzamelingen van $3$ elementen, want de som van $3$ elementen van de getallen $502$ tot $670$ is altijd kleiner dan 2010 (de grootste som is $2007$). wanneer je als één van de $3$ elementen een getal groter of gelijk aan $1006$ kiest, kun je onmogelijk nog aan $2010$ of eronder geraken. met vier elementen of meer zijn er ook geen slechte deelverzamelingen, aangezien de kleinst mogelijke som groter is dan $2010$.
$B$ is een beneluxverzameling
geen slechte deelverzamelingen van $2$ elementen, omdat de getallen die $671$ tot $1005$ aanvullen tot $2010$ zich niet in $B$ bevinden en je niet $2$ keer $1005$ mag nemen en het kan niet dat beide getallen groter zijn dan $1005$.
Vanaf $3$ elementen kunnen we ook gerust zijn, de kleinste som is al groter als $2010$.
conclusie: onweerlegbaar dat $n=2$ $\blacksquare$