Combinatorics problem on $k$ sets and partionning a set of numbers

46 Views Asked by At

consider $2k+1$ real numbers satisfying the property such that any $2k$ of them can be partitioned into two $k$ sets which exist that the sum of the numbers in each of the sets are equal. Prove that all the numbers are equal.

1

There are 1 best solutions below

2
On

First you can see easily all numbers are even or all numbers are odd. If you take $a+k_1+k_2$ is even, its mean a is even because $k_1=k_2$ thus $k_1 + k_2 = 2\cdot k_1$ which is even. The sum $a+ k_1 +k_2$ is the sum of all numbers and must be all time even or all time odd. Let say $a$ was odd, than the hole sum is odd, so when you take $b + k'_1+k'_2$ you see $b$ is also odd.

Now regardless to that, lets say they are not all equal. So there is at least one pair on numbers such that $a < b$. Lets take the ones that minimize the subtraction, I mean look for the minimum $a-b$ while $a-b>0$. Now you get $a, k_1=k_2$ and $b,k'_1=k'_2$.

Now I may not explain it well, and English is not my native so excuse me.. In the first configuration, b is in one of the groups $k_1$ or $k_2$, lets say $b\in k_1$. Swap $b$ and $a$ so you get the configuration $b, k_1\cup a,k_2$. Now try to move numbers from $k_1 \cup a$ to $k_2$ and in the other way to make them into 2 groups equal to each other (suppose to get $k'_1$ and $k'_2$ or other configuration that can hold it). But because you took $a-b$ to be the minimum, you won't be able to do it. The proof from here is on you :)