# Converting decimal to binary

Problem:

Is it possible to partition the numbers 1-100 into two sets, such that no number in either set will be double any other number in the same group?

Solution:

There are many solutions. Here's one: Try to put every number in the first set, and only put a number in the second set if you have to. You'll find that all the odd numbers will appear in the first set. So we've placed every odd number. Now we have to place all the even numbers. Every even number can be expressed as even * odd. But we also know that odd * odd = odd, so we only need to figure out how to distribute the even multiples of odd numbers. All the doubles of the odd numbers must go in the second set. The quadruples of the odd numbers, therefore must go in the first set. The sextuples in the first set, and so on, alternating in this way. We can express every whole number $$m,$$ in the form $$m = 2^kd,$$ where $$d$$ is some odd number. When $$k$$ is even, we put $$m$$ in the first set, and when $$k$$ is odd, we put $$m$$ in the second set. The number $$2^k,$$ in binary, is a 1, followed by $$k$$ zeros. Thus, $$2^kd$$ is $$d$$ followed by $$k$$ zeros. Thus, we have another way of deciding the set to which $$m$$ belongs. If the binary representation of $$m$$ has an even number of trailing zeros, put $$m$$ in the first set. If it has an odd number of trailing zeros, put $$m$$ in the second set.

Going further:

What if, instead of avoiding doubles, we wanted to avoid triples? quadruples? What's the general strategy, if any?