Let be given $32$ positive integers with the sum $120$, none of which is greater than $60.$ Prove that these integers can be divided into two disjoint subsets with the same sum of elements.
Problem
Source: 12-th Hungary-Israel Binational Mathematical Competition 2001
Tags: combinatorics proposed, combinatorics
Justyo
08.08.2008 22:56
We suppose that it's impossible to do the sets. We suppose that every number is different. Every number is less than 60, then, they have different congruences (mod 60). If we have a number with congruence $ a$ and another with congruence $ - a$, the result becomes trivial (we put the two numbers on a set, and all the others in the another one, the both groups have 60 as sum of elements), then we know that the congruence of the numbers are on the set: $ {0,\pm 1,\pm 2,...,\pm 29, 30}$ But, there are 32 numbers, and there are 31 different congruences, then there are two numbers that have the opposite congruence, and we put that numbers on a set, and the others on the another one. Then, there are at less two equal numbers. (to be continued) If anything is not understood, let me know, i'm sorry for having a poor english.
EverGreenShadow
10.08.2008 22:17
"We suppose that every number is different." Then we cannot make 120 sum of positive 32 integers.
alphachapmtl
24.11.2008 18:33
Justyo wrote: ...then we know that the congruence of the numbers are on the set: $ {0,\pm 1,\pm 2,...,\pm 29, 30}$ But, there are 32 numbers, and there are 31 different congruences, then there are two numbers that have the opposite congruence, and we put that numbers on a set, and the others on the another one. ... Quote: note that 2 numbers can't both have congruence 0, cause those 2 numbers would have to be 60 and 60, which already sum to 120.
Justyo
01.12.2008 21:03
I've seen what I post after I posted, and I realize the stupid thing I made. Later, I found an strategy, but I didn't make a demostration of this... Since you remember me this problem, I will try to remember the strategy for you:
You call $ a_1 \leq a_2 \leq ... \leq a_{32}$ the numbers. You put $ a_{32}$ in a first subset. In the next step, you put $ a_{31}$ and $ a_{30}$ in a second subset. If $ a_{31}+a_{30} > a_{32}$ then we put $ a_{29}$ in the subset with $ a_{32}$, if not, we put $ a_{29}$ with $ a_{31}$ and $ a_{30}$. In every step, we put $ a_k$ in the subset with the smaller sum. If the two subsets are equal, we can choose, it's the same thing. When we finish (we put $ a_1$) the two subsets are equal...
If I have a good memory, this is the strategy, and it look it works, but I don't really know how to prove it, and I totally forgot the problem after doing this... I post this because no one post nothing, then maybe someone gets inspired by my strategy :p (And as I said in posts before, excuse my poor english...)