2

Assmue that the set $$S=\{a_{1},a_{2},\cdots,a_{8}\}, 1\le a_{i}< 100,a_{i}\in N$$

there for any subset $A=\{b_{1},b_{2},\cdots,b_{p}\}$ and $B=\{c_{1},\cdots,c_{q}\},A\neq B$ (mean that $A\subset S,b\subset S$)

and such $$b_{1}+b_{2}+\cdots+b_{p}\neq c_{1}+c_{2}+\cdots+c_{q}$$

find a set $S$ such this condition

My try: I consider sometimes,and I take $$S=\{1,8,16,32,64,92,94,98\}$$ then I take $$A=\{32,64,94\},B=\{92,98\},\mbox{it is clear}A\subset S,B\subset S$$ but such $$32+64+94=92+98$$ so this example is not such it

and then take other example $$S=\{8,16,32,64,92,93,98,99\}$$ I take $$A=\{92,99\},B=\{93,98\},A\subset S,B\subset S$$ but such $$92+99=93+98$$ so this example is not such it?

so Now I can't find this example such this condition,can you someone help me

and I think this problem is interesting.

Community
  • 1
math110
  • 93,304
  • The obvious solution is to use the powers of $2$. The difficulty in the problem is the $a_i<100$ condition, which prevents this. – Jack M May 10 '14 at 01:01

2 Answers2

2

Try $ \{ 99, 98, 97, 95, 92, 86, 75, 52 \}$.

Consider $x_i = 99 - a_i$, we have $X = \{ 0, 1, 2, 4, 7, 13, 24, 47 \}$. Since the sum of $x_i$ is 98, which is less than 99, this shows us that if any 2 subsets of $A$ have the same sum, they must have the same number of elements.

Then, it remains to check that no 2 (non-intersecting) subsets of $X$ with the same number of elements have the same sum. This check is easy, by considering the largest element in the subset. For example, if the largest element in a subset is 47, then the other set needs at least $24+13+7+4$ (since $24+13+7= 44 < 47$, and it can't have more than 5 elements), and so the original set's sum must be $47+0+1+2$, which is too large.

For a simiar question, see this.

Calvin Lin
  • 68,864
1

Take $S=\{3,6,12,24,48,95,96,97\}=\{3\cdot 2^k, 0\leq k\leq 5\}\cup\{3\cdot2^5-1,3\cdot2^5+1\}=A\cup B$.

Since the sums from all power of $2$ up to $2^5$ will range from $1$ to $63$, we have that sums of element in $A$ will be of the form $3t$, for $1\leq t\leq 63$.

This gives us $63$ different numbers that are at most $189$. Note that they are $0\mod 3$.

Next we have numbers formed by taking $95$ and any (or none) of the $3\cdot2^k$ numbers. This will give $64$ new numbers, new because they are $-1 \mod 3$.

We also have the $64$ numbers that are $1\mod 3$ formed by taking 97 and any or none of $A$'s.

Finally, we have the $64$ formed by taking $95+97=192$ and any or none of $A$. These are alos $0\mod 3$ numbers, but they are at least $192$ and so, are different than our $63$ first numbers.

We then have $63+3\cdot 64=255$ different sums from elements in $S$. Since $S$ has $2^8-1=255$ non-empty subset, it follows that no two subsets have equal sum.

Bonus: Show that it is impossible to find a set $S$ with $9$ elements smaller than $100$ that has this property.

See problem $4$ here for the above proof and the answer to the bonus question.

Jean-Sébastien
  • 4,623
  • 1
  • 17
  • 39