MathDB

Bijection of natural numbers

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

May 6, 2013

floor functioninductionvectorGaussnumber theoryrelatively primenumber theory proposed

Problem Statement

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.

Back to Problems View on AoPS