Suppose $a_{1} < a_{2}< \cdots < a_{2024}$ is an arithmetic sequence of positive integers, and $b_{1} <b_{2} < \cdots <b_{2024}$ is a geometric sequence of positive integers. Find the maximum possible number of integers that could appear in both sequences, over all possible choices of the two sequences. Ray Li
Problem
Source: USA TST 2024 P5
Tags: USA TST 2024, USA TST, number theory
15.01.2024 20:00
The answer is $11$, with equality when $a_i=i$ and $b_i=2^{i-1}$. Let $d=a_2-a_1$ and $r=\frac{b_2}{b_1}$. Lemma: Let $p$ be a prime. Then $\nu_p(a_i)$ takes on at most $2+\lfloor\log_p(2023)\rfloor$ distinct values. Proof: If $\nu_p(d) > \nu_p(a_1)$ then there is only $1$ value. Otherwise, we have $\nu_p(a_i)>\nu_p(d)+\lfloor\log_p(2023)\rfloor$ for at most one $i$ and $\nu_p(d)\le \nu_p(a_j)\le \nu_p(d)+\lfloor\log_p(2023)\rfloor$ for all remaining numbers, as desired. Now by the lemma, if there are at least $12$ numbers $c_1,\dots,c_{12}$ in both sequences, then $r=2$ and the first $11$ $c_i$ have consecutive $\nu_2$ values. If one of $a_1$ and $a_2$ is not among the $c_i$, then $2^{10}\le \frac{a_{2024}}{a_3}\le \frac{2023}{2}$, absurd. Hence $a_2=2a_1$, so $a_i=ia_1$ for all $i$, and there are actually only $11$ distinct $\nu_2$ values among the $a_i$, as desired.
15.01.2024 20:39
Assume wlog that $b_1=m^k$ and $b_{k+1} = n^k$ are the 1st and last elements of $b$ that are in $a$. Let $b_{x_1},\dots,b_{x_r}$ be the elements of $b$ that are in $a$. Assume wlog that $\gcd(x_1,\dots,x_r)=1$. Then, the common difference $d$ of $a$ divides $n-m$. So, \[b_{k+1}-b_1\le 2023d\]\[m^k-n^k \le 2023(m-n)\]\[m^{k-1}+m^{k-2}n+\dots+n^{k-1} \le 2023\]\[1+\dots+2^{k-1}\le 2023\]\[k\le 10\]\[k+1\le 11.\]Therefore, there are at most $11$ shared elements between the two sequences. This is achieved when $a_i=i$ and $b_i=2^{i-1}$.
15.01.2024 21:05
me when p4 takes two hours and p5 takes five minutes
15.01.2024 22:30
The same answer should hold without the condition that the elements be positive integers.
15.01.2024 22:39
The answer is $11$, achieved when $a_i=i$ and $b_i=2^{i-1}$. Let $\tfrac{p}{q}>1$ be the common ratio of the $b_i$, where $p>q$ are relatively prime positive integers. Then $q^{2023} \mid b_1$, so we can write $b_1=kq^{2023}$ for some $k \in \mathbb{Z}^+$ and thus $b_i=kp^{i-1}q^{2024-i}$ for all $i$. Now suppose there exist twelve indices $i_1<\cdots<i_{12}$ where $b_{i_x}$ also appears in $a_i$. Let $d>0$ be the common difference of the $a_i$. We should have $$2023d=a_{2024}-a_1 \geq b_{i_{12}}-b_{i_1}=kp^{i_1-1}q^{2024-i_{12}}(p^{i_{12}-i_1}-q^{i_{12}-i_1}).$$On the other hand, $d$ should always divide $b_{i_x}-b_{i_y}$ for any $1 \leq y<x \leq 12$. Since $\gcd(p,q)=1$, the gcd of these expressions across all suitable $(x,y)$ is equal to $$kp^{i_1-1}q^{2024-i_{12}}\gcd(p^{i_x-i_y}-q^{i_x-i_y})_{1 \leq y<x \leq 12}.$$Because $(i_2-i_1)+(i_3-i_2)+\cdots+(i_{12}-i_{11})=i_{12}-i_1$, there exist some $y<x$ (specifically where $x=y+1$) such that $t:=i_x-i_y \leq \tfrac{i_1-i_{12}}{11}$. Thus $$d \leq kp^{i_1-1}q^{2024-i_{12}}(p^t-q^t),$$but also $$2023d \geq kp^{i_1-1}q^{2024-i_{12}}(p^{11t}-q^{11t}),$$since $f(t):=p^t-q^t$ is increasing for any $p>q>1$ (by taking a derivative), so $$2023(p^t-q^t) \geq p^{11t}-q^{11t} \implies p^{10}+\cdots+q^{10} \leq p^{10t}+\cdots+q^{10t} \leq 2023.$$The minimum of $p^{10}+\cdots+q^{10}$ clearly occurs when $(p,q)=(2,1)$, but in this case it equals $2047>2023$: contradiction. Thus at most $11$ integers appear in the both sequences. $\blacksquare$
20.01.2024 19:52
27.02.2024 12:57
The most moronic USATST ever.
16.03.2024 17:03
Let $x$ and $y$ be relatively prime positive integers such that $b_n=\frac{x^n}{y^n}B$. Let $s_1, s_2, \dots, s_k$ be an increasing sequence such that $b_{s_k}$ are the terms the two sequences have in common. We get that $b_{s_{k+1}}-b_{s_k}=\frac{B(x^{s_{k+1}}-x^{s_k}y^{s_{k+1}-s{k}})}{y^{s_{k+1}}}$. If $y>1$ then the $v_{y}(b_{s_{k+1}}-b_{s_k})$ is decreasing so we can have no more than $11$ terms. If $y=1$ then $b_{s_{k+1}}-b_{s_k}=B(x^{s_{k+1}}-x^{s_k})$ so $v_{x}(b_{s_{k+1}}-b_{s_k})$ is increasing so we can have no more than $11$. This is achieved with $\{1, 2, 4, \dots\}$ and $\{1, 2, 3, \dots\}$.
27.11.2024 03:22
The answer is $11$, attained by taking $a_i = i$ and $b_i = 2^{i-1}$. Claim: The terms common to both sequences form a geometric sequence (as opposed to if the terms in common, were, say, $b_1, b_4, b_{14}, b_{25}$ or something like that). Proof: This follows from taking the sequence $b_1, b_2, \dots, b_{2024}$ modulo $d$, where $d$ is the common difference of $a_i$. (This still works even if the common ratio of $b_i$ is not defined modulo $d$, left as an exercise to the reader.) Now, take the geometric sequence of common terms and divide them by their GCD. It suffices to show that an arithmetic sequence containing the terms \[a^k, a^{k-1} b, \dots, ab^{k-1}, b^k\]has at least $2^k$ total terms, where $\gcd(a,b) = 1$. The difference between the first two terms is $a^{k-1} (b-a)$ while the difference between the last two terms is $b^{k-1} (b-a)$. Therefore, the common difference of this arithmetic sequence divides $b-a$, so there are at least \[1 + \frac{b^k-a^k}{b-a} \geq 1 + \frac{(a+1)^k - a^k}{(a+1)-a} \geq 2^k.\]
29.11.2024 05:00
For each $1\le k\le 2024$, let $a_k = x+y(k-1)$ for positive integers $x,y$ and let $b_k = Cz^{k-1}w^{2024 - k}$ for positive integers $C,z,w$ with $\gcd(z,w) = 1$ and $z > w$. Suppose there are $s$ shared terms; that is, there exist $c_1 < \dots, c_s$ and $d_1 < \dots < d_s$ with \[ x + y(c_i - 1) = Cz^{d_i - 1}w^{2024 - d_i}\]for each $i = 1,\dots, s$. In particular, we have $y(c_s - c_1) = Cz^{d_s - 1}w^{2024 - d_s} - Cz^{d_1 - 1}w^{2024 - d_1} (\spadesuit)$. Claim: the function $f(x,y) = Cx^{d_s - 1}y^{2024 - d_s} - Cx^{d_1-1}y^{2024 - d_1}$ is nondecreasing for all $(x,y)\in\mathbb{R}^2$ with $x \ge y > 0$. proof: Note that $$\partial_x f(x,y) = C(d_s-1)x^{d_s - 2}y^{2024-d_s} - C(d_1-1)x^{d_1-2}y^{2024-d_1} \ge \frac{1}{x}(d_1-1)f(x,y),$$which is clearly nonnegative since $f(x,y)$ is nonnegative due to $x > y$. Similarly, \[ \partial_y f(x,y) = C(2024-d_s)x^{d_s-1}y^{2023-d_s} - C(2024-d_1)x^{d_1-1}y^{2023 -d_s}\ge \frac{1}{y}(2024-d_s)f(x,y) \ge 0\quad \square\] Now revisit $(\spadesuit)$. Due to the fact that $w\ge 1$ and $z\ge 2$, we can use the claim to obtain \[y(c_s-c_1) = f(z,w) \ge f(2,1) = C(2^{d_s - 1} - 2^{d_1 - 1}).\]But we have $y(c_s - c_1)\le 1\cdot (2024 - 1) = 2023$ obviously. Also, $C(2^{d_s - 1} - 2^{d_1 - 1}) \ge 1(2^{d_s - 1} - 2^{d_s - s}) \ge 2^{s-1}- 1$. Hence, $2^{s-1}\le 2024$, so $s\le 11$. This lower bound is easily achieved by $C = 1, z = 2, w = 1, x = 1, y = 1$, so the answer is indeed $\boxed{11}$.