# Relations in a set

• Sep 5th 2010, 08:10 AM
atreyyu
Relations in a set
Hello,
Given is a positive integer \$\displaystyle k\$. Prove that out of every set of integers which has more than \$\displaystyle 3^k\$ elements one can pick out a sub-set \$\displaystyle S\$ with \$\displaystyle k+1\$ elements and the following quality:
for any two subsets \$\displaystyle A,B\subseteq S\$ the sum of all elements in A is different from the sum of all elements in B.

I've been trying to play with base-system representation for a while but it leads me nowhere. Your help will be appreciated.
• Sep 5th 2010, 10:43 AM
Pim
I'm not sure about this, but I do have an idea about how you could approach this. Maybe you can prove that there is a subset you can make such that all numbers are "out of reach". For example, for k = 3 and the set is all numbers up until 27, the numbers 1, 4, 9 and 27 satisfy S.
Maybe if you order them and pick the \$\displaystyle 3^0\$th, \$\displaystyle 3^1\$th, \$\displaystyle 3^2\$th, \$\displaystyle 3^3\$th, etc. ?
• Sep 5th 2010, 11:42 AM
atreyyu
Ok, but these numbers don't have to start with 1 and increment by 1, they can be any numbers, including negatives.
• Sep 5th 2010, 10:03 PM
Pim
Yeah, I know. Hence the "maybe if you order them".
I have no idea how to actually prove this, but this was something that sprang to mind.