Problem

Source: Indian IMOTC 2013, Practice Test 1, Problem 3

Tags: floor function, induction, vector, Gauss, number theory, relatively prime, number theory proposed



We define an operation $\oplus$ on the set $\{0, 1\}$ by \[ 0 \oplus 0 = 0 \,, 0 \oplus 1 = 1 \,, 1 \oplus 0 = 1 \,, 1 \oplus 1 = 0 \,.\] For two natural numbers $a$ and $b$, which are written in base $2$ as $a = (a_1a_2 \ldots a_k)_2$ and $b = (b_1b_2 \ldots b_k)_2$ (possibly with leading 0's), we define $a \oplus b = c$ where $c$ written in base $2$ is $(c_1c_2 \ldots c_k)_2$ with $c_i = a_i \oplus b_i$, for $1 \le i \le k$. For example, we have $7 \oplus 3 = 4$ since $ 7 = (111)_2$ and $3 = (011)_2$. For a natural number $n$, let $f(n) = n \oplus \left[ n/2 \right]$, where $\left[ x \right]$ denotes the largest integer less than or equal to $x$. Prove that $f$ is a bijection on the set of natural numbers.