Let $p,q$ be positive integers. For any $a,b\in\mathbb{R}$ define the sets $$P(a)=\bigg\{a_n=a \ + \ n \ \cdot \ \frac{1}{p} : n\in\mathbb{N}\bigg\}\text{ and }Q(b)=\bigg\{b_n=b \ + \ n \ \cdot \ \frac{1}{q} : n\in\mathbb{N}\bigg\}.$$The distance between $P(a)$ and $Q(b)$ is the minimum value of $|x-y|$ as $x\in P(a), y\in Q(b)$. Find the maximum value of the distance between $P(a)$ and $Q(b)$ as $a,b\in\mathbb{R}$.
Problem
Source:
Tags: number theory, Sets, maximum value, romania, Romanian TST
07.06.2021 14:47
Fix some $a,b\in \mathbb{R}$ and let us look for a better understanding of the $\textit{distance}$ between $P(a)$ and $Q(b)$. We have $$a_m-b_n=a+\frac mp-b-\frac nq=(a-b)+\left(\frac mp-\frac nq\right)=(a-b)+\frac{mq-np}{pq}.$$Now we look at what values the fraction $\frac{mq-np}{pq}$ may achieve. We need the following preliminary result: $\textbf{Lemma}$. Let $a,b\in \mathbb{N}^*$ such that $\gcd(a,b)=1$. Then for some $m,n\in \mathbb{N}^*$ we have $am-bn=1$. Let us return to what we are looking for. Denote $d=\gcd(p,q)$ and let $p=p'd$, $q=q'd$; then $\gcd(p',q')=1$. Our fraction becomes: $$\frac{mq-np}{pq}=\frac{m\cdot dq'-n\cdot dp'}{d^2p'q'}=\frac{mq'-np'}{dp'q'}=\frac{mq'-np'}{\text{lcm}[p,q]}.$$From our lemma, there exist $m',n'\in \mathbb{N}^*$ such that $m'q'-n'p'=1$. Therefore, our fraction may become $\frac{1}{\text{lcm}[p,q]}$. For $m=km'$ and $n=kn'$, $k\in \mathbb{N}$, it also attains the value $$\frac{km'q'-kn'p'}{\text{lcm}[p,q]}=k\cdot\frac{m'q'-n'p'}{\text{lcm}[p,q]}=\frac{k}{\text{lcm}[p,q]}.$$We may do the same thing all over again (by considering $m''$ and $n''\in \mathbb{N}^*$ such that $n''p'-m''q'=1$) and deduce that the fractions $$\frac{k}{\text{lcm}[p,q]}$$with $k\in \mathbb{Z}_{\le 0}$ may be obtained too. Therefore, we can see that all the values $\frac{mq-np}{pq}$ may get are exactly the fractions of the type $$\frac{k}{\text{lcm}[p,q]},~~k\in \mathbb{Z},$$since they are the only possible to be obtained. All these being said, th distance between $P(a)$ and $Q(b)$ is the minimum of the expression $$\left \lvert(a-b)+\frac{k}{\text{lcm}[p,q]}\right \rvert,$$where $k\in \mathbb{Z}$ can be anything. A closer look tells us the following thing: the least value the above expression can take is actually the distance from $(b-a)$ to the closest fraction of the form $\frac{k}{\text{lcm}[p,q]}$. We know that $(b-a)$ lies between $2$ consecutive such fractions, so this minimum cannot be greater than $$\frac{1}{2\text{lcm}[p,q]}.$$This is attainable, for example any $a,b\in \mathbb{R}$ with $$b-a=\frac 12\left(\frac{k}{\text{lcm}[p,q]}+\frac{k+1}{\text{lcm}[p,q]}\right)=\frac{2k+1}{2\text{lcm}[p,q]},~~k\in \mathbb{Z}$$work fine.
07.06.2021 14:50
oVlad wrote: Let $p,q$ be positive integers. For any $a,b\in\mathbb{R}$ define the sets $$P(a)=\bigg\{a_n=a \ + \ n \ \cdot \ \frac{1}{p} : n\in\mathbb{N}\bigg\}\text{ and }Q(b)=\bigg\{b_n=b \ + \ n \ \cdot \ \frac{1}{q} : n\in\mathbb{N}\bigg\}.$$The distance between $P(a)$ and $Q(b)$ is the minimum value of $|x-y|$ as $x\in P(a), y\in Q(b)$. Find the maximum value of the distance between $P(a)$ and $Q(b)$ as $a,b\in\mathbb{R}$. Sniped. Cute problem. I claim that the answer is $\boxed{\frac{1}{2 \cdot \text{lcm}(p,q)}}$. One can check that \[ \text{dist}(P(a),Q(b)) = \min_{m,n \in \mathbb{N}} \left| a - b + \frac{m}{p} - \frac{n}{q} \right|\]Actually, let's extend $m,n \in \mathbb{N}$ to $m,n \in \mathbb{Z}$ by checking that \[ \frac{m}{p} - \frac{n}{q} = \frac{m - p}{p} - \frac{n - q}{q} = \frac{m + p}{p} - \frac{n + q}{q} \] We will now claim that for $m,n \in \mathbb{Z}$, then the set of values for $\frac{m}{p} - \frac{n}{q}$ is precisely the set of values of $\frac{\ell}{\text{lcm}(p,q)}$, where $\ell \in \mathbb{Z}$. To prove this, note that \[ \frac{m}{p} - \frac{n}{q} = \frac{mq - np}{pq} = \frac{\ell \cdot \gcd(p,q)}{pq} = \frac{\ell}{\text{lcm}(p,q)} \]by Bezout's Theorem. So, we conclude that \[ \text{dist}(P(a), Q(b)) = \min_{\ell \in \mathbb{Z}} \left| a - b + \frac{\ell}{\text{lcm}(p,q)} \right| \] Now, suppose that there exists $a,b \in \mathbb{R}$ such that $\text{dist}(P(a), Q(b)) > \frac{1}{2 \cdot \text{lcm}(p,q)}$. By definition, we have \[ \min_{\ell \in \mathbb{Z}} \left| a - b + \frac{\ell}{\text{lcm}(p,q)} \right| > \frac{1}{2 \cdot \text{lcm}(p,q)} \]However, if $a > b$, replace $\ell$ with $\ell - 1$ to attain a contradiction. If $a < b$, replace $\ell$ with $\ell + 1$ to attain a contradiction. Hence, \[ \text{dist}(P(a), Q(b)) \le \frac{1}{2 \cdot \text{lcm}(p,q)}. \]For equality, just check that $a = \frac{1}{2 \cdot \text{lcm}(p,q)}, b = 0$ works fine because \[ \min_{\ell \in \mathbb{Z}} \left| \frac{1}{2 \cdot \text{lcm}(p,q)} + \frac{\ell}{\text{lcm}(p,q)} \right| = \min_{k \in \mathbb{Z}} \left| \frac{2k + 1}{2 \cdot \text{lcm}(p,q)} \right| \ge \frac{1}{2 \cdot \text{lcm}(p,q)} \]