Home | Back to Contest Questions
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

 

 

Are you Confused ?

Do you need assistance?

 

Let our Experts Help you:         

 
Copyright @Mathyards 2003-2004