|
Problem 6. Let m ≥ 2 be an integer, A be a finite set of (not necessarily positive) integers, and B1,B2,B3,...,Bm be subsets of A. Assume that for each k = 1,2,...,m the sum of the elements of Bk is mk. Prove that A contains at least m/2 elements.
proposed by Austria
|
|
Solution
Let  and  .
By the given condition, for all  , we have  for some  .
Thus, for every integer  , writing  for  , we obtain
![\[mx = \displaystyle\sum_{i=1}^{m}c_{i}m^{i} = \displaystyle\sum_{i=1}^{m}c_{i}\left(\displaystyle\sum_{j=1}^{k}b_{i,j}a_{j}\right) = \displaystyle\sum_{j=1}^{k}(\displaystyle\sum_{i=1}^{m}c_{i}b_{i,j})a_{j} = \displaystyle\sum_{j=1}^{k}d_{j}a_{j}\]](//latex.artofproblemsolving.com/6/3/e/63ea7d8bf7e64f55a7b09856ce4ca3defcfc02ca.png) for some integers  .
Hence, the RHS must take at least  distinct values, which implies
![\[m^{m} \le [m(m-1)+1]^{k} < m^{2k}\]](//latex.artofproblemsolving.com/7/f/d/7fdf2e91a93722cacd0e86df21e809f578346134.png) which immediately gives  .
|
|
and 
.
,
for some 
.
,
for 
,![\[mx = \displaystyle\sum_{i=1}^{m}c_{i}m^{i} = \displaystyle\sum_{i=1}^{m}c_{i}\left(\displaystyle\sum_{j=1}^{k}b_{i,j}a_{j}\right) = \displaystyle\sum_{j=1}^{k}(\displaystyle\sum_{i=1}^{m}c_{i}b_{i,j})a_{j} = \displaystyle\sum_{j=1}^{k}d_{j}a_{j}\]](http://latex.artofproblemsolving.com/6/3/e/63ea7d8bf7e64f55a7b09856ce4ca3defcfc02ca.png)
for some integers 
.
distinct values, which im![\[m^{m} \le [m(m-1)+1]^{k} < m^{2k}\]](http://latex.artofproblemsolving.com/7/f/d/7fdf2e91a93722cacd0e86df21e809f578346134.png)
which immediately gives 
.