There are $n\geq2$ weights such that each weighs a positive integer less than $n$ and their total weights is less than $2n$. Prove that there is a subset of these weights such that their total weights is equal to $n$.
Problem
Source: Turkey TST 1989 - P5
Tags: inequalities proposed, inequalities
11.09.2013 19:43
You don't need the weights to have weight less than $n$.
11.09.2013 19:53
Let these weight-integers be $w_1,w_2,\dots,w_n$ with $\sum w_i=S<2n$. Take the numbers $w_1$, $w_1+w_2$, $\dots$, $S-w_n$, $S$. These $n$ numbers either have one divisible by $n$ (1), or two congruent with each other mod $n$ (2). If (1) is the case, the result follows immediately. In case (2), take the difference of the two sums congruent with each other. This difference will be $n|$ and $0<$, $2n>$, so therefore it is $n$. Done.
11.09.2013 21:12
Now prove the result stays true if the sum of the weighs is $2n$, when $n$ is an even positive integer.
11.09.2013 22:59
We have integers $x_i$ for which $x_1+x_2+\dots+x_n=2n$ and $x_i\le n$ $\forall i=1,2,\dots,n$. If $x_1=\dots=x_n=2$, we are done. Suppose that $x_1\neq x_2$, and check the sums \[x_1,x_1+x_2,x_1+x_2+x_3,\dots,x_1+x_2+\dots+x_{n-1}.\] If there is a sum that is divisible by $n$, or two that are congruent to each other mod $n$, we are finished based on the original solution. The remaining case is when the above sums are pairwise incongruent mod $n$. Then just substitute $x_2$ for $x_1$ at the beginning of the list and we are finished. Note that this is the most we can say with respect to $n$ and $x_i\le n$ - the result isn't true for odd $n$ ($x_1=\dots=x_n=2$), or $\exists x_i>n$ ($x_1=n+1$, $x_2=\dots=x_n=1$).
11.09.2013 23:53
I read the original problem and a total overkill of a solution instantly crossed my mind. Add $n-1$ null weights to the $n$ weights we have. Now the result follows trivially from Erdős–Ginzburg–Ziv theorem(a simple consequence of Cauchy-Davenport). The above-mentioned theorem states that from every $2n-1$ integers we can pick $n$ integers such that $n$ divides their sum. In our problem, that sum is greater than $0$ since we have only $n-1$ $0$'s, and lesser than $2n$ so it must be $n$, hence we're done. However I don't see an obvious way to extend this approach to the problem posted by mavropnevma.
12.09.2013 00:18
@odnerpmocon: interesting corollary of E-G-Z, but yes, overkill. There is a saying that it is not a good idea to shoot a sparrow with a cannon. You tried to kill a snail with an ICBM. There is also another generalization. Suppose the sum of $(q-1)n+1$ positive integers is $qn$. Then these integers can be partitioned into $q$ groups of equal sums. By the rules of the forum, we should continue this here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=553612.