Rational sequences

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#1 h Apr 30, 2009, 8:08 PM • 6 Y

Y by GoodMorning, Adventure10, Mango247, and 3 other users

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$ .

This post has been edited 1 time. Last edited by v_Enhance, Dec 7, 2015, 3:14 PM
Reason: Eliminate \minus, \equal

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JSteinhardt

947 posts

JSteinhardt

#2 h Apr 30, 2009, 9:15 PM • 8 Y

Y by 277546, Illuzion, Adventure10, Stuffybear, Mango247, and 3 other users

Paul Christiano's solution:

Click to reveal hidden text

This post has been edited 2 times. Last edited by JSteinhardt, May 1, 2009, 12:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Yongyi781

2142 posts

Yongyi781

#3 h Apr 30, 2009, 9:20 PM • 2 Y

Y by starchan, Adventure10

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sdkudrgn88

168 posts

sdkudrgn88

#4 h Apr 30, 2009, 9:51 PM • 6 Y

Y by jbala, Adventure10, Mango247, and 3 other users

My (arrogantly claimed to be) elegant solution

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.

This post has been edited 1 time. Last edited by sdkudrgn88, Apr 30, 2009, 9:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aznlord1337

130 posts

aznlord1337

#5 h Apr 30, 2009, 9:54 PM • 2 Y

Y by Adventure10, Mango247

? 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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

andersonw

652 posts

andersonw

#6 h Apr 30, 2009, 9:54 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Yongyi781

2142 posts

Yongyi781

#7 h Apr 30, 2009, 9:55 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by Yongyi781, Apr 30, 2009, 9:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jmerry

12096 posts

jmerry

#8 h Apr 30, 2009, 9:56 PM • 2 Y

Y by Adventure10, Mango247

This was a fun one.

Here's my approach:
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sdkudrgn88

168 posts

sdkudrgn88

#9 h Apr 30, 2009, 9:56 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chelseafc

18 posts

chelseafc

#10 h Apr 30, 2009, 11:02 PM • 2 Y

Y by Adventure10, megarnie

Wasn.t able to solve anything of this question.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Yongyi781

2142 posts

Yongyi781

#11 h Apr 30, 2009, 11:17 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

maru

93 posts

maru

#12 h May 1, 2009, 12:16 AM • 2 Y

Y by Adventure10, Mango247

I'm not sure if this is correct, but here's my approach:

Click to reveal hidden text

I feel like I'm not getting something right.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JSteinhardt

947 posts

JSteinhardt

#13 h May 1, 2009, 12:20 AM • 2 Y

Y by Adventure10, Mango247

By the way, the solution I posted was by Paul Christiano.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Yongyi781

2142 posts

Yongyi781

#14 h May 1, 2009, 12:22 AM • 2 Y

Y by Adventure10, Mango247

Indeed, $r=1$ is not supposed to be the number you're getting...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jmerry

12096 posts

jmerry

#15 h May 1, 2009, 12:36 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheStrangeCharm

290 posts

TheStrangeCharm

#44 h Jan 13, 2015, 11:34 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Taha1381

816 posts

Taha1381

#45 h Aug 30, 2018, 6:54 AM • 2 Y

Y by Adventure10, Mango247

A purly p-adic solution also exist.I am on the phone now I will edit the post to show my solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rmtf1111

698 posts

rmtf1111

#46 h Oct 12, 2018, 5:32 PM • 3 Y

Y by e_plus_pi, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#47 h Sep 7, 2019, 7:14 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aryan-23

558 posts

Aryan-23

#48 h Nov 13, 2020, 6:29 PM • 3 Y

Y by tigerzhang, starchan, anurag27826

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 !

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathlogician

1051 posts

mathlogician

#49 h Feb 20, 2021, 3:42 AM

Y by

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.

This post has been edited 3 times. Last edited by mathlogician, Feb 20, 2021, 3:48 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5003 posts

IAmTheHazard

#50 h Jul 12, 2021, 6:23 PM • 1 Y

Y by centslordm

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)$ .

We now prove the following claim, the purpose of which is to avoid issues with the fact that multiplying infinitely many rationals doesn't necessarily give a rational number. We will use the fact that if $q$ is rational and nonzero, then there are finitely many primes $p$ with $\nu_p(q) \neq 0$ (proof).

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IvoBucata

46 posts

IvoBucata

#51 h Nov 19, 2021, 8:45 AM

Y by

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.

This post has been edited 1 time. Last edited by IvoBucata, Nov 19, 2021, 8:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GoodMorning

826 posts

GoodMorning

#52 h Dec 24, 2022, 2:38 AM

Y by

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.

This post has been edited 2 times. Last edited by GoodMorning, Dec 24, 2022, 2:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

480 posts

kamatadu

#53 h Feb 9, 2023, 3:45 PM • 1 Y

Y by HoripodoKrishno

wrong soln :noo:

@below, you are totally correct, sorry for the flawed solution

This post has been edited 1 time. Last edited by kamatadu, Feb 10, 2023, 12:07 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HoRI_DA_GRe8

598 posts

HoRI_DA_GRe8

#55 h Feb 9, 2023, 4:26 PM • 1 Y

Y by kamatadu

kamatadu wrote:

Lol, this was locked from the past 2 days so couldn't post back then

Page 1

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

thdnder

198 posts

thdnder

#56 h Oct 3, 2023, 3:15 PM

Y by

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$

This post has been edited 1 time. Last edited by thdnder, Feb 6, 2024, 5:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4190 posts

john0512

#57 h Dec 24, 2023, 10:49 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

280 posts

peppapig_

#58 h Feb 24, 2024, 5:13 PM

Y by

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.

This post has been edited 1 time. Last edited by peppapig_, Feb 24, 2024, 5:14 PM
Reason: Parentheses

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1748 posts

OronSH

#59 h May 7, 2025, 10:25 PM

Y by

Shift to $s_1=t_1=0$ . Then $s_it_i$ is an integer, and $(s_i-s_j)(t_i-t_j)$ is an integer implies $s_it_j+s_jt_i$ is an integer. Now $s_it_j,s_jt_i$ sum and multiply to integers, and they are rational, so they are integers.

If prime power $p^k$ is in the denominator of some $s_i$ then it divides all $t_i$ , so in particular only finitely many are possible. Similarly if prime power $q^\ell$ is in the denominator of $t_i$ it divides all $s_i$ . (Notice no prime occurs in both.)

Now choosing $r=\frac{\prod p^k}{\prod q^\ell}$ works.

This post has been edited 1 time. Last edited by OronSH, May 7, 2025, 10:26 PM

Z K Y