CWMO 2014 Problem 8

Given a real number $q$ , $1 < q < 2$ define a sequence $\{x_n\}$ as follows: for any positive integer $n$ , let $$x_n=a_0+a_1 \cdot 2+ a_2 \cdot 2^2 + \cdots + a_k \cdot 2^k (a_i \in \{0,1\}, i = 0,1, \cdots m k)$$ be its binary representation, define $$x_k= a_0 +a_1 \cdot q + a_2 \cdot q^2 + \cdots +a_k \cdot q^k.$$ Prove that for any positive integer $n$ , there exists a positive integer $m$ such that $x_n < x_m \leq x_n+1$ .