vraagje (wiskunde)
 

hey,

hoeveel elementen moet een deelverzameling van{1,2,...,999} minstens hebben om alleszins 2 elementen met som 1000 te bevatten? Kan iemand mij helpen?

Grts

Als 2 elementen a en b de som 1000 hebben moet gelden: b=1000-a. Laat k een gegeven element van {1,2,...,999} zijn en laat a de waarden 1 t/m k aannemen, dan zal b de waarden 1000-k t/m 999 aannemen. Dit geeft voor een gegeven k dus 2*k elementen dat de deelverzameling zal bevatten.

Moet je het niet bewijzen voor willekeurige deelverzamelingen, dus niet alleen voor verzamelingen met opvolgende getallen?

Niet dat ik dan het bewijs weet, maar het lijkt me dat dat wel nodig is.

501 elementen, lijkt me.

In deze verzameling van 1000 elementen heb je immers 500 keer een 'koppel' waarbij de som precies 1000 is (1+999, 2+998, ...)

In het 'slechtste geval' pak je precies 500 elementen waarvan er onderling geen enkele twee samen in zo'n koppel voorkomen, met 501 elementen heb je er dus altijd 2 inzitten waarvan de som 1000 is.

Klopt als een bus. :)