Let $s_1, s_2, s_3, \dots$ be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \dots.$ Suppose that $t_1, t_2, t_3, \dots$ is also an infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
Problem
Source: 2009 USAMO problem 6
Tags: number theory, greatest common divisor, Hi
01.05.2009 00:15
Paul Christiano's solution:
01.05.2009 00:20
The second half of his solution matched my first half, but my second half didn't match his first half due to me blanking out and being unable to continue further (So I ended up writing junk for the second half)
01.05.2009 00:51
I probably got one point docked because in my written solution I wrote that $ s_1t_1$ had to be an integer, which it didn't.
01.05.2009 00:54
? What JSteinhardt means is that given any pair of infinite sequences which satisfies the property, you can obviously subtract or add the same amt from each term (they would cancel). Similarly you can say divide every element in s by k and divided all elements in t by k and it still has the property. Obviously this is reversible.
01.05.2009 00:54
sdkudrgn88 wrote: No, we can't. What if none of the s_n and t_n are zero? The sequences are an infinite number of rational numbers, but they don't have to be all of them. For all we know, it's the harmonic series, or one of the terms are 1 while the others are all 2/7...the problem only said they couldn't all be the same, so it could oscillate between two, etc... We can translate it, though, because if you subtract or add anything to all of the terms of the sequence, it still preserves all of the differences. Edit: Sorry, should have checked before posting.
01.05.2009 00:55
But in the infinite case, $ r$ might either be (1) infinity, or (2) an irrational number. So proving it for "arbitrarily large $ n$" doesn't work, as I showed someone else who made this assumption.
01.05.2009 00:56
This was a fun one. Here's my approach:
01.05.2009 00:56
aznlord1337 wrote: ? What JSteinhardt means is that given any pair of infinite sequences which satisfies the property, you can obviously subtract or add the same amt from each term (they would cancel). Similarly you can say divide every element in s by k and divided all elements in t by k and it still has the property. Obviously this is reversible. Oops... I removed the comment from my own post after I realized what he meant. Yongyi781 wrote: But in the infinite case, $ r$ might either be (1) infinity, or (2) an irrational number. So proving it for "arbitrarily large $ n$" doesn't work, as I showed someone else who made this assumption. That means I didn't get any of the problems at all. Wahhh... well, there's always next year.
01.05.2009 02:02
Wasn.t able to solve anything of this question.
01.05.2009 02:17
Actually, to prove that $ r$ was indeed rational and not infinity or irrational, all you needed to show was that there are a finite number of prime factors between the denominators of $ s_i-s_j$ and $ t_i-t_j$ for all $ i$ and $ j$, i.e. there are not an infinite number of prime factors in the denominators of these two matrices.
01.05.2009 03:16
I'm not sure if this is correct, but here's my approach:
I feel like I'm not getting something right.
01.05.2009 03:20
By the way, the solution I posted was by Paul Christiano.
01.05.2009 03:22
Indeed, $ r=1$ is not supposed to be the number you're getting...
01.05.2009 03:36
To maru: Yes, it's wrong. maru wrote: Since $ x$ is relatively prime to $ y$, we can divide it out, leaving $ s_i\cong s_j \mod{y}$. No, you can't. This only works if you have beforehand that $ s_i$ and $ s_j$ are integers. Furthermore, that $ \frac{s_ix}{y}$ and $ \frac{s_jx}{y}$ have the same fractional part is simply that $ (s_i-s_j)\frac{x}{y}=(s_i-s_j)(t_i-t_j)$ is an integer, something you knew from the start. Your post represents no progress on the problem.
01.05.2009 03:43
bleh. oh well, I can try next year.
01.05.2009 04:13
Edit: Thanks jmerry (smacks head )
01.05.2009 04:15
Gaping hole: We want one $ r$ that works for all $ i$ and $ j$. Your procedure gets a different $ r$ for each pair.
01.05.2009 06:32
Anyone want to check this solution? It's sketchy.
01.05.2009 07:01
It looks complete and accurate to me. I'd quibble with your use of "factors" and "nonfactors" when, for example, we can have $ p^2$ in one place and $ p$ in another to get an excess of $ p$. If it's what you put on the test, expect most of the points, but not necessarily all.
08.06.2014 05:49
^ Yeah that looks fine. It was pretty simple for a #6 I think. Here's my phrasing of more or less the same thing. Like everyone else, shift $s_1 = t_1 = 0$, and WLOG assume $s_2 \neq 0$. Call a scaling an operation where we multiply $\{s_n\}$ by some rational amount and divide $\{t_n\}$ by the same amount. Then perform a scaling so that $s_2 = 1$. Now observe that for any $i$, $j$ we have $s_it_i \in \mathbb Z$ and also $s_it_j + s_jt_i \in \mathbb Z$. In particular, $t_2$ is an integer, say $t$. Note that if $s_3 = \frac ab \neq 0$ for $(a,b) = 1$ and $t_3 = \frac ba \cdot r$ for some $r \in \mathbb Z$ then $t \cdot \frac ab + r \cdot \frac ba$, implying $b \mid t$. That therefore means all denominators in $\{s_n\}$ divide $t$. Thus if we scale $\{s_n\}$ by the LCM of all their denominators, we arrive at a situation where $s_n \in \mathbb Z$ for all $n$, and $\{s_n\}$ has no common divisor. Now we claim that all the $\{t_n\}$ must be integers, which then completes the problem. Assume not, and that for some $k$, $t_k = \frac ab \neq 0$ with $(a,b) = 1$ and $p \mid b$ for a prime $p$. Then $p \mid s_k$, but we can also select an $s_\ell$ not divisible by $p$, meaning $t_\ell$ does not have $p$ in its denominator. Now $s_\ell t_k + s_k t_\ell$ is an integer, but looking at the $p$-adic evaluation this is clearly impossible.
14.01.2015 01:34
The condition only depends on the difference of the elements of the sequence, so we can assume $s_1 = t_1 = 0$. Also, there is some $x$ so that $s_x$ is non-zero. Then multiplying all of the $s_i$ by $\frac{1}{s_x}$ and multiplying all of the $t_i$ by $s_x$, so we assume that $s_x = 1$, for some $x$. Note that because $s_1 = t_1 = 0$, the condition easily tells us that $s_i t_i$ is an integer for all $i$. Note that $-(s_i t_j + s_j t_i) = (s_i - s_j)(t_i - t_j) - s_i t_i - s_j t_j$, which tells us that $s_i t_j + s_j t_i$ is an integer for all $i$ and $j$. But note that $s_i t_j s_j t_i$ is also an integer. Thus, $s_i t_j$ and $s_j t_i$ are both rational roots of some monic quadratic polynomial with integer coefficients, which tells us that they are algebraic integers which means they must be integers themselves (this also follows from the rational root theorem). Now, taking $i = u$, we get that $t_j$ is an integer for all $j$. Let $d$ be the greatest common denominator of all of the $t_i$. Then divide all of the $t_i$ by $d$ and multiply all of the $s_j$ by $d$. Clearly all of the $t_i$ are still integers, but actually we have that all of the $s_j$ are all integers now as well. To see this, note that we can express $d$ as an integer linear combination of all of the $t_i$ by bezout's lemma, but then $ds_i$ is clearly an integer because $s_i t_j$ is an integer for all $i$ and $j$, so we are done.
30.08.2018 09:54
A purly p-adic solution also exist.I am on the phone now I will edit the post to show my solution.
12.10.2018 20:32
If rationals $a$ and $b$ satisfy $a+b\in \mathbb{Z}$ and $ab \in \mathbb{Z}$ then clearly both $a$ and $b$ are integers, this is a quick application of Rational Root Theorem. $(\bigstar)$ Let $r$ be an integer such that $M=r(t_2-t_1)$, $N=r(s_2-s_1)$ and $C=r(s_1t_1-s_2t_2)$ are integers. $$(s_i-s_1)(t_i-t_1) \in \mathbb{Z} \ \ \text{and} \ \ (s_i-s_2)(t_i-t_2) \in \mathbb{Z} $$$$\implies s_i(t_2-t_1)+t_i(s_2-s_1)+s_1t_1-s_2t_2 \in \mathbb{Z} \implies Ms_i+Nt_i+C \in \mathbb{Z}$$Mind that $MN(s_i-s_j)(t_i-t_j) \in \mathbb{Z}$ for any $i$ and $j$.$$Ms_i+Nt_i+C \in \mathbb{Z} \ \ \text{and} \ \ Ms_j+Nt_j+C \in \mathbb{Z} \implies $$$$\implies M(s_i-s_j)N(t_i-t_j) \in \mathbb{Z} \ \ \text{and} \ \ M(s_i-s_j)+N(t_i-t_j) \in \mathbb{Z} \stackrel{(\bigstar)}{\Longrightarrow} M(s_i-s_j) \in \mathbb{Z}$$And the conclusion easily follows.
07.09.2019 10:14
We begin with an important technical lemma. Lemma: Suppose \begin{align*} \nu_p(a)+\nu_p(b)&\ge 0 \\ \nu_p(c)+\nu_p(d)&\ge 0 \\ \nu_p(a\pm c)+\nu_p(b\pm d)&\ge 0 \end{align*}for any of the four possible choices of sign for the last inequality. Then, we have \[\nu_p(a)+\nu_p(d),\nu_p(b)+\nu_p(c)\ge 0.\] Proof: By symmetry, it suffices to show that $\nu_p(a)+\nu_p(d)\ge 0$. Suppose for sake of contradiction that we had $\nu_p(a)+\nu_p(d)<0$. Then, $\nu_p(c)\ge-\nu_p(d)>\nu_p(a)$, so \[\nu_p(a+c)=\nu_p(a).\]Also, $\nu_p(b)\ge-\nu_p(a)>\nu_p(d)$, so \[\nu_p(b+d)=\nu_p(d).\]Thus, \[\nu_p(a+c)+\nu_p(b+d)=\nu_p(a)+\nu_p(d)<0,\]which is the desired contradiction. $\blacksquare$ From this, we derive the following extraordinary claims. Claim (Weak): For any $i,j,k$, we have \[\nu_p(s_i-s_j)+\nu_p(t_j-t_k)\ge 0.\] Proof: Apply the lemma with $a=s_i-s_j$, $c=s_j-s_k$, $b=t_i-t_j$, and $d=t_j-t_k$, with the signs for the third inequality chosen to be $+,+$. $\blacksquare$ Claim: For any $i,j,k,\ell$, we have \[\nu_p(s_i-s_j)+\nu_p(t_k-t_\ell)\ge 0.\] Proof: Apply the previous claim and the lemma with $a=s_i-s_j$, $c=s_i-s_\ell$, $b=t_i-t_k$, and $d=t_k-t_\ell$, with the signs for the third inequality chosen to be $-,+$. $\blacksquare$ The problem is all but destroyed at this point. The final claim tells us that $(s_i-s_j)(t_k-t_\ell)$ is an integer for all $i,j,k,\ell$. For convenience, we'll rephrase the problem as having two sequences $(S_i)$ and $(T_j)$ such that $S_iT_j\in\mathbb{Z}$ for all $i$ and $j$, with our goal being to show that there exists a rational number $r$ such that $S_ir$ and $T_j/r$ are always integers. Note that for any $i$ and fixed $j$, there exists an integer $k$ such that $S_i=k/T_j$. Thus, the number of prime that can be in the denominator of any $S_i$ is finite, and same with $T_j$. Let $P$ be the (finite) set of all primes in the denominators of all $T_i$ and $S_j$. Furthermore, for any $p\in P$, the equation $S_i=k/T_j$ guarantees that $\nu_p(S_i)$ is bounded below. Let $r_p$ be this minimum value. Then, $\nu_p(T_j)\ge -r_p$, as $S_iT_j$ is an integer where $i$ is such that $\nu_p(S_i)=r_p$. Now, let $r=\prod_{p\in P}p^{-r_p}$. We see that for all $p\in P$, $\nu_p(S_ir)\ge 0$ and $\nu_p(T_j/r)\ge 0$. Again, since only primes in $P$ appear in the denominators of $S_i$ and $T_j$, this forces $S_ir$ and $T_j/r$ to always be integers, as desired.
13.11.2020 21:29
First we note a easy fact. If rationals $a,b$, satisfy $a+b , ab \in \mathbb Z$, then $a,b \in \mathbb Z$. Proof : Define $f(x)= x^2-(a+b)x+ab)$. On one hand, $f(x)\in \mathbb Z[X]$, so $a,b \in \overline {\mathbb Z}$. Also $a,b \in \mathbb Q$. This gives $a,b \in \mathbb Q \cap \overline {\mathbb Z}\equiv \mathbb Z$, so the lemma holds. We shift such that $s_1=t_1=0$. Also scaling the $s_i,t_i$'s doesnt change the truth of the statement, so WLOG $s_2=1$. Next note that $s_it_i\in \mathbb Z$ and $s_it_j+s_jt_i \in \mathbb Z$ for all $i,j \in \mathbb N$. Using the fact on $s_it_j$ and $s_jt_i$, we get $s_it_j\in \mathbb Z$, for all $i,j$. This directly gives that $t_j$ are integers for all $j$. Note that $t_i\cdot s_j$ is a integer. This gives that the denominator of the $s_i$'s divides $t_j$ for all $i,j$. So divide the $t_i$ by their gcd and multiply the $s_i$ by the same and we are happy !
20.02.2021 06:42
Solution with lots of help from @above. First we can subtract some rational from all the $s_i$ such that $s_1=0$, and similarly $t_1 = 0$. Moreover by multiplying each $s_i$ appropriately we can assume $s_n=1$ for some $n$. It follows that $s_it_i$ is an integer for all $i$, and as a result $s_it_j + s_jt_i$ is also an integer. But also $s_is_jt_it_j$ is an integer, so we can conclude that $s_it_j$ is an integer for all pairs $(i,j)$. (Here's a $\nu_p$ argument to see this: let $a = \nu_p(s_it_j)$ and $b = \nu_p(s_jt_i)$. Note that $\min(a,b) \geq 0$ is true unless $a=b$; but then $a+b \geq 0$ implies $a,b \geq 0$ anyways.) Let $e$ be the minimal $\nu_p$ of all the numbers in $\{s_i\}$: we will show that $\nu_p(t_i) \geq e$ for all $i$. But note that $\nu_p(s_it_j) \geq 0$ for all pairs $(i,j)$, done.
12.07.2021 21:23
For rational numbers $a,b$, we write $a\equiv b \pmod{k}$ if $k \mid a-b$, where $k$ is an integer. This replaces the conventional modulo meaning with all those inverses. We begin with the following claim: Claim 1: For any prime $p$, the quantity $\nu_p(t_i-t_j)$ across all $i,j$ is bounded below. Proof: I will prove that $\nu_p(t_i)$ across all $i$ is bounded below. Suppose otherwise. Then, there exist infinitely many positive integers $k>1$ such that $\nu_p(t_k)<\nu_p(t_i)$ for all $i<k$. Call such indices "mountainous". For every mountainous index $k$, we have $\nu_p(t_k-t_i)=\nu_p(t_k)$ for all $i<k$. It follows that for such $k$, we have $\nu_p(s_k-s_i)\geq -\nu_p(s_k)$ for all $i<k$. Then, for all $i,j<k$, $$\nu_p(s_i-s_j)=\nu_p((s_k-s_j)-(s_k-s_i))\geq -\nu_p(s_k).$$But since $-\nu_p(s_k)$ is unbounded above as $k$ grows large, it follows that $\nu_p(s_i-s_j)$ isn't bounded, so $s_i-s_j=0$. This implies $(s_n)$ is a constant sequence, which violates the condition. Thus $\nu_p(t_i)$ is bounded below, so $\nu_p(t_i-t_j)\geq \min\{\nu_p(t_i),\nu_p(t_j)\}$ is bounded below. $\blacksquare$ Of course, this claim also applies to $\nu_p(s_i-s_j)$.
. Claim 2: There are finitely many primes $p$ such that the minimum of $\nu_p(t_i-t_j)$ over all $i,j$ is nonzero. Proof: Suppose otherwise. Then there are either infinitely many primes $p$ such that $\min\{\nu_p(t_i-t_j)\}$ is positive or infinitely many $p$ such that the quantity is negative. However, the former is impossible, since it would then follow that there are infinitely many $p$ such that $\nu_p(t_i-t_j)$ is positive for all $i,j$, so $t_i-t_j=0$ for all $i,j$ and $(t_n)$ is constant: contradiction. Thus we would need infinitely many $p$ with $\min\{\nu_p(t_i-t_j)\}<0$. As $\nu_p(t_i-t_j) \geq \min\{\nu_p(t_i),\nu_p(t_j)\}$, we would then have infinitely many $p$ with $\min\{\nu_p(t_i)\}<0$. By the first claim, for such $p$ $\min\{\nu_p(t_i)\}$ is bounded below, so let $\min\{\nu_p(t_i)\}$ be $f(p)<0$. Also let $S(p)$ denote the set of indices $i$ such that $\nu_p(t_i)=f(p)$. Pick some $k \in S(p)$. Then for all $i \neq j \not \in S(p)$, we have $$\nu_p(t_k-t_i)=\nu_p(t_k-t_j)=f(p),$$so $\nu_p(s_k-s_i)=\nu_p(s_k-s_j)\geq -f(p)$. It follows that $\nu_p(s_i-s_j)\geq -f(p)$ for all $i,j \not \in S(p)$, so $\nu_p(s_i-s_j) \geq -f(p)>0$ where $i$ and $j$ are not both in $S(p)$. If there exist $i \neq j$ such that $i,j$ are not both in $S(p)$ for infinitely many primes $p$, then $\nu_p(s_i-s_j)$ is positive for infinitely many primes $p$, which is impossible. Hence for every pair $(i,j)$ with $i \neq j$, there are finitely many primes $p$ such that $i,j$ are not both in $S(p)$, and thus infinitely many primes $p$ such that $i,j$ are both in $S(p)$. But this implies that there are infinitely many primes $p$ such that $i \in S(p)$ for all $i$, which means $\nu_p(t_i)=f(p)<0$ for infinitely many $p$. This is, however, impossible, as $t_i$ is rational. $\blacksquare$ Observe that multiplying every element of $(s_n)$ by some rational $q$ and dividing every element of $(t_n)$ by $q$ changes nothing. Now, let $S$ be the set of all primes $p$ such that $\min\{\nu_p(t_i-t_j)\}$ over all $i,j$ is nonzero, which is finite by claim 2. Let $$q=\prod_{p \in S} \min\{\nu_p(t_i-t_j)\},$$which is rational as $S$ is finite. Then, multiply all elements of $(s_n)$ by $q$ and divide all elements of $(t_n)$ by $q$. We can also shift $(s_n)$ and $(t_n)$ such that $s_1=t_1=0$. After this transformation, I claim $r=1$ works. Since $\min\{\nu_p(t_i-t_j)\}=0$ for all $p$, it follows that $(t_i-t_j)/r=t_i-t_j$ has nonnegative $\nu_p$ and is therefore an integer. Now let $p$ be an arbitrary prime and let $\min\{\nu_p(s_i-s_j)\}=k$. If $k \geq 0$, then $r=1$ obviously works. Suppose $k<0$. Pick $i \neq j$ with $\nu_p(s_i-s_j)=k$, so $\nu_p(t_i-t_j)\geq -k$. Now for every $n \neq i,j$, we have $$\nu_p(s_i-s_j)=\nu_p((s_n-s_j)-(s_n-s_i))\geq \min\{\nu_p(s_n-s_i),\nu_p(s_n-s_j)\}.$$Since $\nu_p(s_n-s_i)\geq k$ and likewise for $s_j$, this means that either $\nu_p(s_n-s_i)=k$ or $\nu_p(s_n-s_j)=k$. If $\nu_p(s_n-s_i)=k$, then $\nu_p(t_n-t_i)\geq -k$. This also means $\nu_p(t_n-t_j)\geq -k$, otherwise $\nu_p((t_n-t_j)-(t_n-t_i))<-k$, contradicting the fact that it's also at least $-k$. Hence we have $$t_n \equiv t_i \equiv t_j \pmod{p^{-k}}$$for all $n \neq i,j$. But this means $$t_a \equiv t_b \pmod{p^{-k}} \implies p^{-k} \mid t_a-t_b,$$so $\nu_p(t_i-t_j)\geq -k>0$ for all $a,b$, which contradicts $\min\{\nu_p(t_i-t_j)\}=0$. Thus $\min\{\nu_p(s_i-s_j)\}\geq 0$, so $(s_i-s_j)r=s_i-s_j$ is an integer for all $i,j$, as desired. $\blacksquare$
19.11.2021 11:45
Scale both sequences so that $s_1=t_1=0$. This implies that for every $i$ $s_it_i$ is an integer. Take any prime $p$. If for every index $v_p(s_i)\geq 0$ and $v_p(t_i)\geq 0$ we can put $v_p(r)=0$ and we're good $mod p$. Otherwise assume that WLOG there exists an index $a$ such that $v_p(s_q)<0$ and is minimal. Denote by $A$ the set of indices for which we have $v_p(s_{a\in A})=v_p(s_q)$; and by $B$ the set of indices for which $v_p(s_{b\in B})>v_p(s_q)$.Clearly both of these sets are non-empty. Now take any two indices $a\in A$ and $b\in B$. We know that $v_p(s_a-s_b)=v_p(s_q)$, so we need to have $v_p(t_a-t_b)\geq -v_p(s_q)$. Lemma:$v_p(t_x-t_y)=v_p(t_x-t_z-(t_y-t_z))\geq min(v_p(t_x-t_z);v_p(t_y-t_z))$. If $a_1;a_2\in A$ and $b\in B$, then we get that $$v_p(t_{a_1}-t_{a_2})\geq min(v_p(t_{a_1}-t_b);v_p(t_{a_2}-t_b))=-v_p(s_q)$$Analogically, if $b_1;b_2\in B$ and $a\in A$, then we get that $$v_p(t_{b_1}-t_{b_2})\geq min(v_p(t_{b_1}-t_a);v_p(t_{b_2}-t_a))=-v_p(s_q)$$This tells us that $v_p(t_i-t_j)\geq -v_p(s_q)$ and $v_p(s_i-s_j)\geq v_p(s_q)$, thus putting $v_p(r)=-v_p(s_q)$ fixes everything $mod $ $p$. If there is an index $i$ with $v_p(t_i)<0$, then we proceed analogically to the above.
24.12.2022 05:38
Claim 1: $v_p(s_i-s_j)$ is bounded below for all $p$, across all $i, j$; the same is true for $\{t_i\}$. Proof: If its unbounded below, then take terms $(s_i, s_j, s_k)$ such that $v_p(s_i-s_j) = -a$ and $v_p(t_i-t_j) = b$ where $b \ge a > 0$, and $v_p(s_j-s_k) \le -69420 b$. Clearly, $v_p(t_j-t_k) \ge 69420b$. Yet, $$v_p(s_i-s_k) = v_p((s_i-s_j) + (s_j - s_k)) = \min(v_p(s_i-s_j), v_p(s_j - s_k)) \le -69420b$$$$v_p(t_i-t_k) = v_p((t_i-t_j) + (t_j - t_k)) = \min(v_p(t_i-t_j), v_p(t_j - t_k)) = b,$$yielding $v_p((s_i-s_k)(t_i-t_k)) < 0$, contradiction. Same result for $\{t_i\}$. $\blacksquare$ Claim 2: Finitely many primes appear in the factorization of denominators of $s_i-s_j$ through all $i, j$; same for $\{t_i\}$. Proof: Assume not. WLOG $t_1 \neq t_2$ (otherwise we can permute the two sequences correspondingly). Take any (of infinitely many) primes $p$ not in the factorization of the denominator of $s_1-s_2$ (note that the following argument works even if this is $0$). Let $s_k$ be the first term such that the factorization of the denominator of $s_k-s_1$ contains $p$. It follows that $s_k-s_2$'s denominator factorization also contains $p$. Thus, $p \mid t_k - t_1$ and $p \mid t_k - t_2$, meaning $p \mid t_1 - t_2$. Since there are infinitely such primes $p$, and $t_1-t_2$ is nonzero, contradiction. $\blacksquare$ Claim 3: Let $S$ be the minimum positive integer such that $S(s_i-s_j)$ is an integer for all $i, j$. This is finite due to the previous claims. Then, all the numerators of $t_i-t_j$ for all $i, j$ are divisible by $S$. Define $T$ similarly and a similar result holds. Proof: Assume FTSOC that there exists $s_i, s_j, t_a, t_b$ and prime $p$ such that $v_p(s_i-s_j) = -\alpha$ and $v_p(t_a-t_b) = \beta$ with $\alpha > 0$ and $\beta < \alpha$. Then, at least one of $v_p(s_a - s_i)$ and $v_p(s_a - s_j)$ is not greater than $-\alpha$. WLOG $v_p(s_a - s_i) \le -\alpha$. Then $v_p(t_a-t_i) \ge \alpha$. Since $v_p(t_a-t_b) = \beta < \alpha$, we have $v_p(t_i-t_b) = \beta$. Meanwhile, $v_p(s_a-s_b) \ge -\beta$. As $v_p(s_a - s_i) \le -\alpha$, we have $v_p(s_i-s_b) \le -\alpha$. Thus, $v_p((t_i-t_b)(s_i-s_b)) \le \beta - \alpha < 0$, contradiction. $\blacksquare$. It follows that setting $r= \frac{S}{T}$ works. We are done.
09.02.2023 18:45
@below, you are totally correct, sorry for the flawed solution
09.02.2023 19:26
kamatadu wrote: Lol, this was locked from the past 2 days so couldn't post back then
handwritten solution images attached There's a problem in this solution, If $S_{\text{min}}=v_p(S_i-S_j)$ then it need not be true that, $t_{\text{min}}=v_p(t_i-t_j)$. You cannot write that, $v_p((S_i-S_j)(t_i-t_j))=S_{\text{min}}+t_{\text{min}}$ My point is if power of $p$ in the sequence $S_i$ be minimum for $S_i-S_j$,then $t_{\text{min}}$ might be equal to $v_p(t_a-t_b)$ where $a,b \not = i,j$. You need to fix this , nice idea by the way
03.10.2023 18:15
Replacing $s_{i}$ to $s_{i} - a$ satisfies problem condition, so WLOG we can assume $s_{0} = t_{0} = 0$. Let $p$ be a prime such that there exists $n$ such that $\nu_{p}(s_n) < 0$. Then since $s_{i}t_{i}$ is integer, so $\nu_p(t_{i}) > -\nu_{p}(s_{i})$. If $j$ is positive integer such that $\nu_{p}(t_{j}) < \nu_{p}(t_{i})$, then $\nu_{p}(t_{i} - t_{j}) = \nu_{p}(t_{j})$. Thus it forces $\nu_{p}(s_{j}) = \nu_{p}(s_{i})$. Then for all $n$ either $\nu_{p}(s_{n}) = \nu_{p}(s_{i})$ or $\nu_{p}(t_{n}) = \nu_{p}(t_{i})$. Thus $p$ cannot be large. Similarly, if $\nu_{p}(t_{n}) < 0$ for some $n$, then $p$ cannot be large. Let $p$ be a prime such that $\nu_{p}(s_{n}) < 0$ for some $n$. Claim: The sequence $(\nu_{p}(s_{n}))$ is bounded below. Proof: Assume the contrary, for large $N$, $\nu_{p}(s_n) \le -N$ for some $n$. Then $\nu_{p}(s_{n} - s_{1}) = -N$ and $\nu_{p}(t_{n} - t_{1}) = \nu_{p}(t_{1})$. So $-N + \nu_{p}(t_{1}) \ge 0$, a contradiction. $\blacksquare$ Let $-M = \inf \nu_{p}(s_n)$. Then we'll show that for all $i, j$, $\nu_{p}(t_i - t_j) \ge M$. Assume the contrary, there is some $i, j$ such that $\nu_{p}(t_i - t_j) < M$. Thus $\min(\nu_{p}(t_i), \nu_{p}(t_j)) \le \nu_p(t_i - t_j) < M$. WLOG, assume $\nu_p(t_i) = \min(\nu_{p}(t_i), \nu_{p}(t_j))$. Then $\nu_p(t_i) < M$. Take $k$ such that $\nu_p(s_k) = -M$. Then $\nu_p(t_k) \le M$. Thus $\nu_p(t_i - t_k) = \nu_p(t_i) < M$. Thus $\nu_p(t_i - t_k) = \nu_p(t_i) < M$. Thus $\nu_p(s_i - s_k) > -M$, so $\nu_p(s_i) = \nu_p(s_k) = -M$. Therefore $\nu_p(t_i) + \nu_p(s_i) < 0$, a contradiction. Therefore taking $r$ such that $\nu_p(r) = -M$ would works.(Since there are finitely many $p$). This completes proof. $\blacksquare$
25.12.2023 01:49
Consider each prime $p$ seperately. Claim 1: For each prime $p$, $v_p(s_i-s_j)$ is bounded below. This is clearly true as otherwise we can pick $(t_1-t_2)(s_i-s_j)$ with $v_p(s_i-s_j)$ arbitrarily low to make it not an integer. Claim 2: There can only be finitely many primes that appear in the denominator of any difference $s_i-s_j$ or $t_i-t_j$ at all. Suppose not. Then, at least one of the difference sets will contain infinitely many primes. Due to this, the numerator of any difference in the other sequence must be divisible by all of these infinitely many primes, contradiction. Thus, consider any prime $p$. Suppose that the minimal $v_p$ of the difference of two terms in $s$ is $k$. By the above claim, $k$ exists, and since the sequence is nonconstant, $k$ is finite. This means that the difference between any two terms of $t$ has to have a $v_p$ of at least $-k$, otherwise the product of that and the one with $v_p$ of $k$ would not be an integer. Thus, if we pick a factor of $p^{-k}$ for $r$, the product of any difference of two terms of $s$ with $r$ would have a nonnegative $v_p$, since we have at least $k$ minus $k$, and for $t$, we would have at least $-k$ plus $k$. Repeating this for all primes $p$ that appear in some denominator gives us a valid value of $r$, since there are only finitely many "concerning" primes.
24.02.2024 20:13
The “finite difference” or “FD” operation on a sequence $a_1$, $a_2$, $\dots$, is defined to be the sequence $a_2-a_1$, $a_3-a_2$, $\dots$, $a_{i+1}-a_i$, $\dots$ Let $a_1$, $a_2$, $\dots$, $a_n$ and $b_1$, $b_2$, $\dots$, $b_n$ be any sequence such that $(a_i-a_j)(b_i-b_j)$ is always an integer for any pair of natural numbers $(i,j)$. If two sequences satisfy this, we will call them “appley”. Apple Claim - I claim that for the sequences $\{c_i\}$ and $\{d_i\}$, where $c_i=a_{i+1}-a_i$ and $d_i=b_{i+1}-b_i$, we must have that \[(c_p-c_q)(d_p-d_q),\]is an integer for any pair of natural numbers $(p,q)$. In other words, $c_i$ and $d_i$ must be appley. First, note that $c_kd_k$ for any natural number $k$ must always be an integer, because we have that \[c_kd_k=(a_{k+1}-a_k)(b_{k+1}-b_k),\]which must be an integer by our assumptions about the two sequences $a$ and $b$. Now, subtraction $c_qd_q$ and $c_pd_p$ from $(c_p-c_q)(d_p-d_q)$, all that is left to prove is proving that $c_pd_q+c_qd_p$ must also be an integer. We will prove this by strong induction. First, we assume that if $|p-q|\leq k$, then $c_pd_q+c_qd_p$ is an integer. Now, we will prove that if $|p-q|=k$, then $c_pd_q+c_qd_p$ must still be an integer. First, note that $c_i+c_{i+1}+\dots+c_{j-1}=a_j-a_i$. Similarly, $d_i+d_{i+1}+\dots+d_{j-1}=b_j-b_i$. Therefore, note that if we have $r$ for some integer $r$; we have that \[(c_r+c_{r+1}+\dots+c_{r+k})(d_r+d_{r+1}+\dots+d_{r+k})=(a_{r+k+1}-a_r)(b_{r+k+1}-b_r),\]must be an integer, since $(a_i-a_j)(b_i-b_j)$ is always an integer for any pair of natural numbers $(i,j)$. However, we can also decompose the sum \[(c_r+c_{r+1}+\dots+c_{r+k})(d_r+d_{r+1}+\dots+d_{r+k}),\]into a sum of many $c_pd_q+c_qd_p$ for $|p-q|\leq k$ and $c_rd_{r+k}+c_{r+k}d_r$. Since the large sum must be an integer and all of the other $c_pd_q+c_qd_p$’s are integers, we conclude that $c_rd_{r+k}+c_{r+k}d_r$ for any natural number $r$, proving our inductive claim. As for our base case, notice that as proved above, we have that $c_pd_p+c_pd_p$ (for $p=q$) must always be an integer since $c_pd_p$ must be an integer. Therefore, if two sequences $a$ and $b$ satisfy that $(a_i-a_j)(b_i-b_j)$, their sequences of their differences $a_2-a_1$, $a_3-a_2$, etc. and similarly for the other one; also satisfy the same condition. Now let us consider the problem conditions $s_i$ and $t_i$. Let us take the first $n$ numbers of the sequences as smaller sequences, namely \[s_1, s_2, \dots, s_n,\]and \[t_1, t_2, \dots, t_n.\]Now allow us to take finite differences of these until one of them converges to a sequence of constant numbers (it will not be a constant sequence of $0$). It is well known that for all finite sequences, they will eventually converge to a constant sequence of length at least $2$ with the constant not being equal to $0$. WLOG, let’s assume that $t_i$ converges first. Let the constant it converges to be called $a$, and assume that this sequence is $k$ numbers long. Note that $s_i$ can converge similarly to a constant, but it does not necessarily have to; so let us consider the finite difference sequence of $s_i$ after applying the finite difference operation the same number of times to be $x_1, x_2, \dots, x_k$. I will now prove that $a(s_i-s_j)$ and $(t_i-t_j)/a$ are always integers using the following two claims. Bapple Claim - Let $m_i$ be the sequence “before” $x_i$ (meaning that in the chain of finite difference operations on $s_i$, applying finite differences on $m_i$ resulted directly in $x_i$). Then I claim that $a(m_i-m_j)$ is always an integer. Note that since $x_i$ and the constant sequence $a$ are appley together by the Apple Claim, we have that $ax_i$ must always be an integer for any $1\leq i\leq k$. Additionally, note that \[m_i=m_1+(x_1+x_2+\dots+x_{i-1}),\]which gives that (WLOG let $j\leq i$) \[m_j-m_i=x_{j-1}+x_{j-2}+\dots+x_{i},\]and multiplying this by $a$ gives a sum of $ax_c$’s for integer $c$’s, meaning that $a(m_i-m_j)$ is always an integer. Catpple Claim - Let $n_i$ be the sequence “before” the constant sequence consisting of $a$’s. Then I claim that $(n_i-n_j)/a$ is always an integer. Note that since the finite differences of $n_i$ are a constant sequence, $n_i$ is an arithmetic sequence with common difference $a$. Therefore, any two numbers in $n_i$ differ by an integer multiple of $a$, meaning that $(n_i-n_j)/a$ is always an integer. Doneapple Claim - For any sequence $e_1$, $e_2$, $\dots$ and any constant $c$, if $c(e_i-e_j)$ is always an integer, then for any sequence $b_1$, $b_2$, $\dots$ that is “before” the $e_i$ sequence, we have that $c(b_i-b_j)$ is always an integer. This can be proved siimlarly to the Bapple Claim by taking sums and then differences. Finally, combining the B, C, and D claims and inducting backwards from the $x_i$ and $a$ constant sequence, we get that $a(s_i-s_j)$ and $(t_i-t_j)/a$ must be integers. We continue taking larger and larger $n$, which in the end yields that the infinite sequence satisfies the same conditions, finishing the problem.