Задача от международната олимпиада !!!!

[dextur33]

Нека М е множество, съставено от 10 естествени числа ненадминаващи 100. Да се докаже, че съществуват две непресичащи се подмножества на М с еднакви суми на елементите си. (Давана на XIV международна олимпиада.)

Моля Ви, помогнете ми с решението ! Благодаря предварително !!!

[drago]

Разглеждаме всички подможества на M. Те са [tex]2^{10} = 1024[/tex]. Като махнем празното остават 1023. За всяко такова подмножество образуваме сумата от елементите му. Получават се 1023 числа всяко от които е по-малко от 10.100=1000. Т.е. има две различни подможества на M с равна сума на елементите си. Като махнем общите им елементи(в сл. че има такива) получаваме исканите 2 непресичащи се множества.