Problem 6

Let

m\ge2

be an integer,

A

a finite set of (not necessarily positive) integers, and

B_1,B_2,B_3,\ldots,B_m

subsets of

A

. Suppose that for every

k=1,2,\ldots,m

the sum of the elements of

B_k

m^k

. Prove that

A

contains at least

m/2

elements.

Step 5 of 6: Count both sides of the injection

Previous step Next step

m^m\le(m(m-1)+1)^{|A|}

Detailed analysis

There are exactly $m^m$ multiples of $m$ in $[0,m^{m+1})$ , namely $X=0,m,2m,\ldots,(m^m-1)m$ , and each maps injectively into the set of $|A|$ -tuples with entries in $\{0,1,\ldots,m(m-1)\}$ , which has $(m(m-1)+1)^{|A|}$ elements. Hence $m^m\le(m(m-1)+1)^{|A|}$ .