2 gelijke sommen

Opgave - IMO 1972 dag 1 vraag 1

Gegeven zijn tien verschillende positieve gehele getallen van twee cijfers.
Bewijs dat men ze kan verdelen over twee verzamelingen zo, dat de som
van de getallen in de ene verzameling gelijk is aan de som van de getallen
in de andere verzameling.

Oplossing

We bepalen eerst hoeveel waarden een som van 1 tot 9 verschillende 2cijferige getallen kan aannemen. de maximale som is $99+98+\dots+91=855$ en minimaal gewoon $10$. Er zijn dus $855-10+1=846$ zulke waarden.

Vervolgens bepalen we, gegeven 10 getallen, het aantal verschillende sommen (met $1$ tot $9$ getallen) die we kunnen bepalen met deze getallen, dit zijn er $2^{10}-2=1022$ (het aantal deelverzamelingen van de verzameling van 10 getallen min de hele verzameling en de lege verzameling)

Wegens DHP (1022>846) zijn er twee verschillende deelverzamelingen die dezelfde som aannemen.

Trek nu de doorsnede van deze 2 verzamelingen af van elk van de verzamelingen, hierdoor bekom je twee verzamelingen van verschillende getallen die tot dezelfde som optellen.