Representing $m$ numbers using partial sums of at most $2^m$

For discussing Olympiad Level Number Theory problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Representing $m$ numbers using partial sums of at most $2^m$

Unread post by rah4927 » Sat Dec 05, 2015 1:19 pm

(1220 Number Theory Problems) Let $m$ positive integers $a_1, \cdots, a_m$ be given. Prove that there exist fewer than $2^m$ positive integers $b_1, \cdots, b_n$ such that all sums of distinct $b_k$s are distinct and all $a_i (i \le m)$ occur among them.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Representing $m$ numbers using partial sums of at most $

Unread post by rah4927 » Tue Dec 08, 2015 4:03 pm

Some hints.
This is a problem where you have to represent some numbers as a sum of some other numbers. We also need any partial sum to be different. This means that we need the $b_i$ to be a sequence of numbers so that adding any subsequence gives a distinct sum, and not only that, we need to be able to represent the $a_i$ as a sum of some $b_i$ too. If you think about this, you should be reminded of using bases to represent the numbers. So let the $b_i$ be $2^1.2^2,2^3,\cdots$ respectively. Then any partial sum is just a base $2$ number and is therefore distinct. However, there is no guarantee that $m<2^n$. This is only half the battle. The rest of the solution is pretty much combinatorial (and a lot more challenging, so try it!).

Post Reply