For nonnegative integers $a$ and $b$, denote their bitwise xor by $a \oplus b$. (For example, $9 \oplus 10=1001_{2} \oplus 1010_{2}=0011_{2}=3$.) Find all positive integers $a$ such that for any integers $x>y \geq 0$, we have  $$ x \oplus a x \neq y \oplus a y . $$
  Answer: the function $x \mapsto x \oplus a x$ is injective if and only if $a$ is an even integer. Even case. First, assume $\nu_{2}(a)=k>0$. We wish to recover $x$ from $c:=x \oplus a x$. Notice that:  - The last $k$ bits of $c$ coincide with the last $k$ bits of $x$. - Now the last $k$ bits of $x$ give us also the last $2 k$ bits of $a x$, so we may recover the last $2 k$ bits of $x$ as well. - Then the last $2 k$ bits of $x$ give us also the last $3 k$ bits of $a x$, so we may recover the last $3 k$ bits of $x$ as well. - ...and so on. Odd case. Conversely, suppose $a$ is odd. To produce the desired collision: Claim - Let $n$ be any integer such that $2^{n}>a$, and define  $$ x=\underbrace{1 \ldots 1}_{n}=2^{n}-1, \quad y=1 \underbrace{0 \ldots 0}_{n} 1=2^{n}+1 . $$  Then $x \oplus a x=y \oplus a y$.   $$ \begin{aligned} & a x=\overline{Q R} \Longrightarrow x \oplus a x=\overline{Q Q} \\ & a y=\overline{P P} \Longrightarrow y \oplus a y=\overline{Q Q} . \end{aligned} $$  We're done.