De Opgave:Kies uit de getallen 1 t/m 100 10 willekeurige getallen (verzameling S). Bewijs dat er altijd twee disjuncte deelverzamelingen A en B te vinden zijn, zodat de som van de elementen in A gelijk is aan de som van de elementen in B. VB: stel S={1,2,3,...,9,10} dan voldoen A={1,4,10} en B={6,9}.
Hoe kun je dit bewijzen?
Stefan
Student universiteit - woensdag 21 februari 2007
Antwoord
Duivenkotprincipe: tel het aantal mogelijke deelverzamelingen uit tien elementen, kijk welke sommen er kunnen zijn en trek je besluit...
Oja: dan heb je nog niet dat A en B disjunct zijn. Maar als je A en B gelijke som hebben kan je gewoon alle gemeenschappelijke elementen eruit halen en dan zijn A' en B' disjunct, en nog altijd gelijke som.
Re: Som van 2 disjuncte verzamelingen is gelijk
