[2.4] Exercise 9
For a given set \(N\) where some element is a power of two times some other element say \(2^ka\) and \(a\), there can exist no set \(M\) such that \(N,M\) is an Euler pair. Why? Let \(2^ka\) be the smallest element of the above mentioned type, and show that \(M\) can be uniquely constructed so that it works successfully for all \(n > 2^ka\) but that the construction will fail for \(n = 2^k\), just as in the above example.

Proof

Assume for the sake of contradiction that \((N,M)\) is an Euler pair and that \(a \in N\) and \(2^ka \in N\) for some \(k \geq 1\). Consider the integer

$$ \begin{align} n = 2^ka \end{align} $$

There are at least two distinct partitions of \(n\) using parts of \(N\): \(s_1 = 2^ka\) and \(s_2 = a + a + \cdots + a\) where we have \(2^k\) copies of \(a\). Since \((N,M)\) is an Euler pair, then there exists a bijection between partitions of \(N\) and partitions of \(M\):

$$ \begin{align} \phi : \{\text{partitions of $n$ with parts in $N$}\} \longrightarrow \{\text{partitions of $n$ into distinct parts from $M$}\}. \end{align} $$

Hence, repeatedly merge pairs from \(s_2\) into \(2a\). Starting from \(2^k\) copies of \(a\), we obtain exactly \(2^ka\). Meanwhile with \(s_1 = 2^ka\), we just stop at \(2^ka\) itself since there is nothing to merge. Therefore, we get that \(\phi(s_1) = \phi(s_2)\) which is a contradiction since \(\phi\) is a bijection.

References