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 6 of 6: Conclude

|A|\ge m/2

Previous step Next step

m^m<m^{2|A|}\ \Rightarrow\ |A|>m/2

Detailed analysis

Since $m(m-1)+1<m^2$ , we get $(m(m-1)+1)^{|A|}<m^{2|A|}$ , so $m^m<m^{2|A|}$ , which gives $m<2|A|$ , i.e. $|A|>m/2$ ; as $|A|$ is an integer, this in particular yields $|A|\ge m/2$ , as required.