Problem:
A positive integer is called stable if it is possible to split the set of all positive divisors of (including and ) into two subsets that have no elements in common, which have the same sum. For example, is stable, because but is not stable. Is stable?
Solutions — 2
Solution 1
Solution:
Yes. In general, let be a number of the form , where is an odd prime less than . We will show that one can form an expression, obtained by adding and subtracting together all the divisors of , which is equal to zero. First note that
The remaining divisors are , whose sum is more than . Thus we are able to write as a sum of some subset of the remaining divisors simply by considering its binary representation. Clearly the unused terms will sum to . But the difference between these two quantities is , just as above. It is now clear how to form the desired expression involving all divisors of which evaluates to zero, and you're done.
If is to be stable, then the factors of can be put on either side of an equal sign, and when these factors are summed, you get an equality. The highest power of that divides will either lie on the same side as , or the opposite side. The key idea of David's solution is the observation that if is stable and the highest power of that divides lies on the opposite side of the equal sign from , then is also stable.
For example, is stable, because
and notice that lies opposite . To show that is stable, we let and exchange places, and then add in the two new factors ( and ), getting
It is easy to see why this method works (verify it!)
The remainder of David's argument looks at , which is not stable, but he successively doubles it, making it more and more balanced, until he shows that is stable. Then the algorithm described above will show that is stable for all .
Solution 2
Solution:
(Sketch) This solution, by David Spies of Albany High School, won the Brilliancy Award, because it used ideas that no other solution had.
If is to be stable, then the factors of can be put on either side of an equal sign, and when these factors are summed, you get an equality. The highest power of that divides will either lie on the same side as , or the opposite side. The key idea of David's solution is the observation that if is stable and the highest power of that divides lies on the opposite side of the equal sign from , then is also stable.