Show that $g(n):=\bigoplus_{k=0}^\infty \left\lfloor\frac{n}{2^k}\right\rfloor$ is the inverse of $f$.

We shall seperately show that $f$ is both injective and surjective. Let $n=(n_1n_2 \ldots n_k)_2 \implies [ \frac{n}{2} ]=(0n_1n_2 \ldots n_{k-1})_2$ So, $f(n)=n \oplus [ \frac{n}{2} ] = ((n_1\oplus 0)(n_2 \oplus n_1) \ldots (n_k \oplus n_{k-1}))$. Injectivity: Suppose that $f(n)=f(m)$. From the above representation, we must have $n_1 \oplus 0 = m_1 \oplus 0 \implies n_1=m_1 \implies n_2 \oplus n_1=n_2 \oplus m_1=m_2 \oplus m_1 = m_2 \oplus 0 \implies n_2=m_2$. Now, as induction hypothesis, suppose that $\forall i \in [1,j], n_i=m_i$. Then, $n_{j+1}\oplus n_j=n_{j+1} \oplus m_j=m_{j+1} \oplus m_j \implies m_{j+1}=n_{j+1}$ and so, $n_i=m_i \forall i \in [1,k] \implies n=m$. Surjectivity: For any given natural $m$, let $m=(m_1m_2 \ldots m_k)_2$. Now, by using the relations, observe that given any $a \in { 0,1 }$, there exists unique $b \in { 0,1 }$ such that $b \oplus a=0$ and also for $b \oplus a=1$. So, we may choose unique $n_1$ such that $n_1 \oplus 0 =m_1$ and then $n_2 \oplus n_1=m_2$ and so on. Therefore we may uniquely choose the digits in the base $2$ representation of a number $n$ such that $f(n)=m$.

Same as dibyo , problems actually looks HARD , but actually when we try to solve it is simple!

This operation is called the nim-sum, used in the theory of the NIM game; in fact it is vector addition over $\mathbb{F}_2$. Batominovski's sweet and short proof is based on having $\left \lfloor \dfrac {\lfloor x \rfloor} {m} \right \rfloor = \left \lfloor \dfrac{x} {m} \right \rfloor$ for all real $x$ and positive integer $m$, so take $x=\dfrac {n} {2^k}$ and $m=2$.

Actually in IMOTCs, the first practice question papers is relatively easy..... Take this Let p and q be relatively prime positive integers. Then $\sum_{i=1}^{q-1}{\left[\frac{ip}{q}\right]=\frac{(p-1)(q-1)}{2}}$ where for any real $x$, $[x]$ denotes the greatest integer not exceeding $x$.

Ahh, the famous Gauss sum (wit a one-liner proof, counting lattice points). Very original

To show bijection, we first show that $f(n)$ is one-one as shown above. Then, we can show that $f^{-1}(n)$ can be found out uniquely for every natural number $n$. Say, $x=(x_1 x_2 \dots x_k)_2$ We have to find $n=(n_1 n_2 \dots n_k)_2$ and show that $n$ is unique for unique choice of $x$. $n=(n_1n_2 \ldots n_k)_2 \implies \left[ \frac{n}{2} \right]=(0n_1n_2 \ldots n_{k-1})_2$ $\Rightarrow (x_1 x_2 \dots x_k)_2=((n_1\oplus 0)(n_2 \oplus n_1) \ldots (n_k \oplus n_{k-1}))_2$ $n_1=x_1$ $n1\oplus n_2=x_2 \\ \Rightarrow n_1\oplus n_1\oplus n_2=n_1\oplus x_2 [\because \textrm{adding from left side}] \\ \Rightarrow n_2=x_1\oplus x_2[\because m \oplus m=0, n_1=x_1]$ Inductively, it follows that, $n_i=x_1\oplus x_2\oplus \dots \oplus x_i$ ---- $(eq. 1)$ Thus, given any binary number $x$, we can find out the digits of $n$ by using $eq .1$

Isn't f(n) the gray code if n?

Nice one $\color{black}\rule{25cm}{1pt}$ We are going to use the fact that every number has a distinct binary representation. Thus we say that $n=\sum_{t=0}^{k}a_t.2^t$ for some natural $k$ and where every $a_t$ is either a $0$ or a $1$. Now let's evaluate $\left\lfloor \frac{n}{2}\right\rfloor$ in terms of binary numbers. We have that: $$\left\lfloor \frac{n}{2} \right\rfloor=\left\lfloor\frac{\sum_{t=0}^{k} a_t.2^t}{2} \right\rfloor=\left\lfloor\sum_{t=1}^{k}a_t.2^{t-1} + \frac{a_0}{2}\right\rfloor$$since $a_0$ is either $0$ or $1$ it really doesn't have an impact on $\left\lfloor \frac{n}{2} \right\rfloor$. Thus we have that: $$\left\lfloor \frac{n}{2} \right\rfloor = \sum_{t=1}^{k}a_t.2^{t-1}$$Now we can calculate $f(n)$, since the upper result easily implies that: $$f(n)=2^{k}+\sum_{t=1}^{k}\left(a_t \oplus a_{t-1} \right).2^{t-1}$$ Obviously we can now set any combination of the possible $k$-tuple $(a_1,a_2,\dots ,a_{k-1},a_k)$ to get the any binary number we want so long it has $k$ positions, where the first digit of the binary number is $1$. Thus this means that $f$ is a surjection on the naturals. But notice that in the argument that it all depends on $a_1$ on how $a_2$ is going to behave is we want a specific binary numbers, then $a_3$ also depends on $a_2$ and so on and so on and since every number has a specific binary number, this implies that for a specific binary number we want to construct using $f(n)$ we must have that $(a_1,a_2,\dots ,a_{k-1},a_k)$ must be fixed, which means that $n$ must be fixed, thus we have that $f$ is injective. Thus we have that $f$ is a bijection.

Somewhat similar to @above's solution, but I feel much simpler than all the sols above. Observe that we can treat $\oplus$ like addition mod 2. So from now on, replace $\oplus$ with $+$ and assume everything is taken mod $2$. Let numbers be written as their digits in binary like $n = a_1,a_2,a_3,...,a_k$ where $a_i \in \{0,1\}$ for all $1 \le i \le k$. $\lfloor \frac{n}{2} \rfloor =0, a_1, a_2, ...., a_{n-1}$. So, $f(n) = 0 + a_1, a_2 + a_1, a_3 + a_2, ..., a_{n-1} + a_{n-2} = a_1, a_1 + a_2, a_2 + a_3, ..., a_{n-1} + a_n$ First, see that $f$ is injective. Suppose $f(x) = f(n)$ and $x = b_1, b_2, ..., b_n$ so $f(x) = b_1, b_1 + b_2, b_2 + b_3, ..., b_{n-1}+b_n$ Comparing the digits one by one, we get that all the digits of $x,n$ are same, so we're done We only now need to show its surjective. But comparing first digits, $a_1$ is uniquely determined and so on, we see that it is indeed surjective. So, $f(n)$ is bijective

And eleven years later, India is killing it at the IMO... We inductively construct the binary representation of $n$ from that of $f(n)$. Note that it can be seen that $f(n)$ and $n$ have the same number of digits (say $d$) in binary, so the $d$th digit of $n$ is 1. Now letting the $k$th digit of $f(n)$ be $f_k$ and that of $n$ be $e_k$ for all $k$, we have $f_k = e_k \oplus e_{k+1}$, and from here given $e_{k+1}$ we can uniquely construct $e_k$. Induction shows that we can construct the entire number. Note that this automatically shows $f$ is injective, as we can check $n$ digit-by-digit from $f(n)$ and see the construction is unique. Further, $f$ is surjective, since this construction always gives a valid base-2 number. Therefore, $f$ is indeed bijective.

o so when u write a number in binary then floor(n/2) is just a right bit shift like if n is 1000101 then floor(n/2) is 100010 say we want to make some binary number C using n xor floor(n/2) clearly the MSB of C and the MSB of n must be the same. then, if we've found the leftmost k bits of n, use the xor of the k+1th bit of C and kth bit of n (from the left) to get the k+1th bit of n an example is C=1000101. clearly n must look like 1XXXXXX. 0 xor 1 is 1 so n must look like 11XXXXX. 0 xor 1 is 1 so n must look like 111XXXX. 0 xor 1 is 1 so n must look like 1111XXX. 1 xor 1 is 0 so n must look like 11110XX. 0 xor 0 is 0 so n must look like 111100X. 1 xor 0 is 1 so n must look like 1111001. we see that 1111001 xor 111100 is 1000101=C, as desired. this works cuz a xor b = c means c xor b = a and stuff ykwim anyways this proves bijectivity so yippee! ^-^