The positive integers are to be partitioned into several sets such that two times an integer and the integer itself do not belong to the same set, and every positive integer belongs to exactly one set. What is the minimum number of such sets required?

Sunday, August 19, 2012

Please email your solutions to puzzles@cotpi.com.

### 7 comments

### Credit

This puzzle is taken from:

- Savchev, Svetoslav; Andreescu, Titu. Mathematical Miniatures. Washington, D.C.: Mathematical Association of America, 2003. 36.

## Raul Miller solved this puzzle:

You need two sets. To find which set an integer belongs in, find the largest power of two which can divide the integer to produce a new integer. Put the integers which have odd largest power of two divisor in one set and the rest in the other set.

## Tim Ophelders solved this puzzle:

Let \(m(n)\) be the power of \(2\) in the prime factorization of \(n\). Define two sets \(A\) and \(B\) such that a positive integer \(x \in A\) if and only if \(m(x)\) is even and \(x \in B\) otherwise. Then every positive integer belongs to one of those sets. Now, for each positive integer \(x\), their double, \(2x\), must be in the other set because \(m(2x) = 1 + m(x)\). Thus, the minimum number of sets required to separate every positive integer from its double is \(2\).

## Simon solved this puzzle:

Write each natural number in its prime factorization form. In the first set are the integers where the prime factorization has an even number of \(2\)s. In the second set are the integers where the prime factorization has an odd number of \(2\)s. Any number in the first set will have it's double in the second set, and vice versa. Therefore the minimum number of such sets required is (2).

## Rino Raj solved this puzzle:

It seems two sets should suffice. The following construction shows this. Let the sets be \(A\) and \(B\). Let \(1\) be in set \(A\). For every successive positive integer, we check if half of it is an integer. If not, put it in set \(A\). If half the number is an integer, put it in the set which does not have that integer. This way, every integer gets placed in a set, and its double is never in the same set.

Alternately, every positive integer can be represented uniquely as \(2^m (2n + 1)\), for non-negative integers \(m\) and \(n\). Let set \(A\) contain all the positive integers where \(m\) is even, and set B contain all integers where \(m\) is odd. It may be noted that doubling changes the parity of \(m\), hence each integer and it's double will be in different sets.

## Wonderwice Margera solved this puzzle:

Two sets are clearly required so that \(1\) and \(2\) for instance lie in different sets. Two sets are also sufficient. Here is how to do it. Call the sets \(s_1\) and \(s_2\). For each integer \(i\), let \(2^{t_i}\) be the largest power of \(2\) that divides it. If \(t_i\) is odd, put \(i\) in \(s_1\), else, put it in \(s_2\).

## Tanny Libman solved this puzzle:

The minimum number of sets required is two. We can split the integers according to how many powers of \(2\) occur in each one's prime factorization. Integers with an even power of \(2\) in their prime factorization (including 2^0, aka odd numbers) go in the first set. Integers with an odd power of \(2\) go in the second set. Now the double of any integer in the first set occurs in the second set, and vice versa. Finally, we know that we can do this with all the positive integers because each integer either has an odd or even power of two in its prime factorization. In addition, we know the sets are mutually exclusive because an integer cannot both have an odd and even power of two.

## David Robertson solved this puzzle:

Every positive integer can be divided by \(2\) repeatedly until division is no longer possible. Count the number of maximum possible divisions (possibly zero) for each integer. Then place integers divisible by two an odd number of times into one set, and the rest (each of which 2 divides into an even number of times) into another. By construction, neither set contains both an element and its double.

A one-set 'partition' would fail (as it would contain \(1\) and \(2\), for example) and so the minimum number of sets required for the partition is \(2\).