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 3 of 6: Bound

f_a(X)

for every

a

and

X

Previous step Next step

0\le f_a(X)\le m(m-1)

Detailed analysis

Since $f_a(X)$ is a sum of at most $m$ digits, each in $\{0,1,\ldots,m-1\}$ , we get $0\le f_a(X)\le m(m-1)$ for every $a\in A$ and every multiple $X$ of $m$ below $m^{m+1}$ .