|
Solution 28
by Anand
Let S be a nice
set. If d is a positive integer such that d divides every member of
S then we can obtain a new nice set T by dividing each member of
S.(Of course the niceness is preserved)
So let me assume that there is at least one odd number in S. (If not
then all numbers can be divided by an appropriate power of 2 to get
an odd number)
If S also contained an even number-
Let n be the number of odd numbers in S
Case 1. n is odd
Consider T=S-{a} where a is even number in S.
Then T contains n odd numbers where n is odd. So T can not be
partitioned into two sets such that they have equal sum. (The parity
of the partitions will be different as one will contain odd number
of odd numbers and other will contain even number of odd numbers)
Case 2. n is even
Consider T=S-{b} where b is odd. THen T contains odd number of odd
numbers hence it can not be 'nicely' partitioned.
Thus all numbers of S are odd.
Let m=|S|. if m is even then m-1 will be odd. So an m-1 element
subset of S will have odd number of odd numbers so it can not be
nicely partitioned
Thus m is odd
if m=1, is trivial
m=3, S={a,b,c} remove c,. then a=b or a+b = 0, impossible
if m=5 let S={a,b,c,d,e} a remove e. So either a+b+c=d
or a+d=b+c (Other possibilites are gone due to the ordering)
if a+b+c=d then remove d. then e>d=a+b+c so {a,b,c,e} can not be
partitioned. (the partition containing e will have a sum too big)
if a+d=b+c then
Remove d, a+b+c=e or e+a=b+c but later is not possible.
Thus a+b+c=e
Remove a. In {b,c,d,e} e
Remove b
In{a,c,d,e}. e
So m=5 is not possible
so m>=7
for m=7
Check that S={1,3,5,7,9,11,13} is Nice.
View other answers by :
bugzpodder
|