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
21-2-2007
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.
Christophe
21-2-2007
#49329 - Bewijzen - Student universiteit