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 1 of 6: Write multiples of

m

in base

m

Previous step Next step

In plain words

Any multiple of $m$ below $m^{m+1}$ has a quotient by $m$ that fits in $m$ base- $m$ digits.

X=\sum_{i=1}^m c_i m^i,\quad c_i\in\{0,1,\ldots,m-1\}

Detailed analysis

If $0\le X<m^{m+1}$ is a multiple of $m$ , then $X/m<m^m$ , so $X/m$ has a base- $m$ expansion with at most $m$ digits, giving $X=\sum_{i=1}^m c_im^i$ with each digit $c_i\in\{0,1,\ldots,m-1\}$ .