A rational number $ x$ is called good if it satisfies: $ x=\frac{p}{q}>1$ with $ p$, $ q$ being positive integers, $ \gcd (p,q)=1$ and there exists constant numbers $ \alpha$, $ N$ such that for any integer $ n\geq N$, \[ |\{x^n\}-\alpha|\leq\dfrac{1}{2(p+q)}\] Find all the good numbers.
Problem
Source: China TST 2007, P2
Tags: floor function, number theory unsolved, number theory
03.01.2009 20:41
April wrote: A national number $ x$ is called good if it satisfies: $ x = \frac {p}{q} > 1$ with $ p$, $ q$ being positive integers, $ \gcd (p,q) = 1$ and there exists constant numbers $ \alpha$, $ N$ such that for any integer $ n\geq N$, \[ |\{x^n\} - \alpha|\leq\dfrac{1}{2(p + q)} \] Find all the good numbers. Could you tell me what \{x^n\} means?
03.01.2009 20:58
tringo wrote: April wrote: A national number $ x$ is called good if it satisfies: $ x = \frac {p}{q} > 1$ with $ p$, $ q$ being positive integers, $ \gcd (p,q) = 1$ and there exists constant numbers $ \alpha$, $ N$ such that for any integer $ n\geq N$, \[ |\{x^n\} - \alpha|\leq\dfrac{1}{2(p + q)} \] Find all the good numbers. Could you tell me what \{x^n\} means? {x} means the fraction part of x. i.e. {x}=x-[x]. For example, {3.6}=0.6, {e}=e-2.. is this what you want to know?
05.01.2009 17:04
Very nice problem! Here is my solution. Thesis:q=1 For $ n\ge N$ we can write $ x^n = a_n + \alpha + \beta_n$ where $ a_n\in\mathbb{Z}$ and $ |\beta_n|\le \frac {1}{2(p + q)}$ It's easy to see that the equality case (i.e. $ |\beta_n| = \frac {1}{2(p + q)}$) is possible only a finite number of times if q>1, so for n large enough we have $ |\beta_n| < \frac {1}{2(p + q)}$ Now $ qa_n - pa_{n - 1} = \alpha (p - q) + \beta_{n - 1}p - \beta_n q$ so $ \alpha (p - q) + \beta_{n - 1}p - \beta_n q$ is an integer. For n large enough $ |\beta_{n - 1}p - \beta_n q| < \frac {1}{2}$ so, since $ \alpha (p - q) + \beta_{n - 1}p - \beta_n q$ is an integer, it must be the nearest integer to $ \alpha (p - q)$ (which is unique since it differs from $ \alpha (p - q)$ of less than $ \frac {1}{2}$), so it doesn't depend on n. Therefore, if we call that integer c we have that, for n large enough, $ qa_n = pa_{n - 1} + c$. If we write $ b_n = (p - q)a_n + c$ we have that $ \{ b_i\}$ (for $ i\ge n_0$) is a sequence of positive integers such that $ qb_n = pb_{n - 1}$ So, for a given n, $ q^k$ divides $ b_n$ for all $ k$ (because $ q^kb_{n + k} = p^kb_n$ and $ (p,q) = 1$) so $ q = 1$. OTOH, if x is integer (and greater than 1), then x is good, so good numbers are integers >1.
05.01.2009 17:29
How did you create the sequence $ b_n$?
05.01.2009 20:13
feliz wrote: How did you create the sequence $ b_n$? I will try to explain my solution better: I define $ a_n=\lfloor x^n \rfloor$ and then I define $ \beta_n= \{ x^n\} -\alpha$ (in my previous post I had only claimed the existance of $ a_n$ and $ \beta_n$ such that $ x^n = a_n + \alpha + \beta_n$, $ a_n\in\mathbb{Z}$ and $ |\beta_n|\le \frac {1}{2(p + q)}$ but it's actually better to simply define them). I proved (in the above post) that it exists an integer $ c$ such that, for n large enough, $ qa_{n}=pa_{n-1}+c$ I wanted to prove that this is impossible if q>1, so I defined $ b_n=(p-q)a_n+c$ and now, since $ qa_{n}=pa_{n-1}+c$, we have that $ qb_n=pb_{n-1}$ which implies q=1 Let me know if there is still something that is not clear.
05.01.2009 21:15
Actually I understood your solution... I am just asking what motivated you to create such sequence.
05.01.2009 23:16
feliz wrote: Actually I understood your solution... I am just asking what motivated you to create such sequence. I have not learnt how to write a solution properly, so it is quite common that nobody understand my solutions (even for very easy problems) Anyway I think that the main idea of the solution is to consider the integer $ q\lfloor x^n \rfloor-p\lfloor x^{n-1} \rfloor$ (this is probably the only way to use the hypothesis that x is a rational number) It is quite logical to define the sequence $ a_n=\lfloor x^n \rfloor$ Once you have proven $ qa_n=pa_{n-1}+c$ you migh notice that "c" is extremely annoying (without "c" it would be easy to write a_n explicitly). There is a standard way of solving this problem: you create another sequence $ b_n=a_n+\lambda$ choosing $ \lambda$ so that in the formula for $ b_n$ you don't have that annoyng "c" anymore. I hope that this answers your question.
06.01.2009 01:53
Yes, this answers... Thanks!
07.01.2009 07:53
April wrote: A national number $ x$ is called good if it satisfies: $ x = \frac {p}{q} > 1$ with $ p$, $ q$ being positive integers, $ \gcd (p,q) = 1$ and there exists constant numbers $ \alpha$, $ N$ such that for any integer $ n\geq N$, \[ |\{x^n\} - \alpha|\leq\dfrac{1}{2(p + q)} \] Find all the good numbers. From this problem, could we generalize it as follow "For any positive non-integer number x and a given real number c, 0<c<1, there always exists a positive integer n such that {x^n} can get as close to c as desired"?
22.05.2013 18:24
In other words,for rational,but not integer $x$ the set $A=\{\{x^n\}:n=1,2,3,...\}$ is dense.But this is not trivial.Can someone prove it?