Suppose that $a$ and $b$ are two distinct positive real numbers such that $\lfloor na\rfloor$ divides $\lfloor nb\rfloor$ for any positive integer $n$. Prove that $a$ and $b$ are positive integers.
Problem
Source: Romania TST 2013 Test 2 Problem 1
Tags: floor function, ratio, limit, number theory, greatest common divisor, inequalities, algebra proposed
27.04.2013 13:52
Lemma : Consider the sequence of positive integers $\left<\frac{\lfloor nb\rfloor}{\lfloor na\rfloor}\right>$ where $n\in T=\{1,10,10^2\ldots\}$. I claim that this sequence is eventually non-increasing. Proof: Suppose for some sufficiently large $n_0\in T$ , $\lfloor n_0b\rfloor=m\lfloor n_0a\rfloor$. Then consider the next integer $n\in T$. Suppose $\alpha_n$ is the $n$th digit in the decimal representation of $a$. Define $\beta_n$ similarly. So, $\lfloor nb\rfloor=10\lfloor n_0b\rfloor+\beta_{n_0}=10\cdot m\lfloor n_0a\rfloor+\beta_{n_0}<(m+1)\lfloor na\rfloor$. This proves the lemma. As, the sequence cannot decrease indefinately, there must exist an integer "$m$" such that infinitely many terms in the above sequence attains that value. Now, note that the integer $m$ the ratio between the terms, is $\le 10$ as while multiplying $\lfloor na\rfloor$ with $m$ there must not be any carry. If $m\ge 5$ all the terms in the decimal representation of $a$ must be $1$ after finitely many terms, viz. $a$ is rational.(We consider this case leter) Hence $m\le 4$. However, we also get that $b=ma$. I think it can be done from here. If both are rationals. Take $n$ to be the product of their denominators.
27.04.2013 14:26
suppose that $\left \lfloor nb \right \rfloor/\left \lfloor na \right \rfloor=t_{n}$ such that all of the numbers of sequence $(t_{n})_{n\geq 1}$ are positive integers we prove that this sequence is convergent , we have $\lim_{n \to \infty }(\left \lfloor nb \right \rfloor/\left \lfloor na \right \rfloor)=\lim_{n \to \infty }((nb-\left \{ nb \right \})/(na-\left \{ na \right \}))=\lim_{n \to \infty }((b-(\left \{ nb \right \}/n)/(a-(\left \{ na \right \}/n))=b/a$ . so $t_{n}$ tends to $b/a$ so for $n\geq M$ we have $t_{n}=t$ an then we have $t\mid \left \lfloor nb \right \rfloor$ for all $n\geq M$ so its obvious that $b\in \mathbb{Z}$ . We prove that $a\in \mathbb{Z}$ too. if $a$ is not an integer number then there are infinitely many numbers $n$ such that $gcd(\left \lfloor na \right \rfloor,n)=1\Rightarrow \left \lfloor na \right \rfloor\mid b$(this statement is proved at the end) for infinitely many numbers $n$ which is a contraction . (let $\left \lfloor na \right \rfloor/n=x_{n}$ this sequence is convergent and tends to $a$ so $\left \{ na \right \}=0$)
27.04.2013 18:35
The proof I arrived at isn't too different from the two already posted here.
that the sequence of integers $\left<\frac{[nb]}{[na]}\right>$ converges to $\frac{a}{b}$. So, $b=ka$ for some $k\in\mathbb{N}$. This also implies that for $n$ greater than or equal to a sufficiently large $n_0$, $\left\{nb\right\}=k\left\{na\right\}$, which leads to the inequality $\left\{na\right\}<1/k \le 1/2\dots(1)$ unless both $a$ and $b$ are integers. But if $a$ and $b$ are not both integers, then we can choose our $n_0$ such that ${n_0}a$ and ${n_0}b$ are not both integers. Then there will exist unique $\alpha\in\mathbb{N}_0$ such that $\frac{1}{2^{\alpha +1}} \le \left\{n_0 a\right\} < \frac{1}{2^\alpha}\dots(2)$. Take $n={2^\alpha}n_0$. $na={2^\alpha}{n_0}a={2^\alpha}[{n_0}a]+{2^\alpha}\left\{{n_0}a\right\}$ From $(2)$, we get $[na]={2^\alpha}[{n_0}a]$ and $\left\{na\right\}={2^\alpha}\left\{{n_0}a\right\} \ge \frac{1}{2}$, which violates $(1)$. This proves that $a$ and $b$ are both integers.
27.04.2013 21:17
Almost the same as above.... $\lim_{n \to \infty} \frac{ \lfloor nb \rfloor }{ \lfloor na \rfloor }=\frac{b}{a}$. So, taking $n$ sufficiently large, we get $b=ax, x \in \mathbb{N}$. Also, $\exists m_0 \in \mathbb{N}$ such that $\forall m \ge m_0,\frac{ \{mb\} }{ \{ma\} } =x$. Then, $\{ma\} \le \frac{1}{x} \implies m_0b=m_0a + c_0 + (x-1)\{ma\}$ and $(m_0+1)b=(m_0+1)a+c_1 +(x-1)\{ma\}$ with $c_0,c_1 \in \mathbb{N}$. These equations give $b=a+c_1 -c_0 \implies b-a\in \mathbb{N}$. Now, $\frac{b}{a} \in \mathbb{N} \implies \frac{b}{a} -1 \in \mathbb{N_0} \implies \frac{b-a}{a} \in \mathbb{N} \implies a \in \mathbb{Q} \implies b \in \mathbb{Q}$. Now, this is easy to deal with.
04.05.2013 12:07
08.07.2013 11:40
IberoAmerican Olympiad, 1997