Determine the greatest positive integer \(n\) for which there exists a sequence of distinct positive integers \(s_1\), \(s_2\), \(\ldots\), \(s_n\) satisfying \[s_1^{s_2}=s_2^{s_3}=\cdots=s_{n-1}^{s_n}.\] Proposed by Holden Mui
Problem
Source: ELMO Shortlist 2023 N2
Tags: Elmo, number theory
29.06.2023 15:13
Very nice, any ideas, i think maximum value of $n$ would be $3$
29.06.2023 16:34
shinhue wrote: Very nice, any ideas, i think maximum value of $n$ would be $3$ $s_1 = 6^6, s_2 = 6, s_3 = 36, s_4 = 18$ works
29.06.2023 21:36
Nice problem. The answer is $n=5$. Claim: if $n>4$ then $s_{n-3}=2,s_{n-2}=16,s_{n-1}=4$. Proof: suppose $s_1^{s_2}=s_2^{s_3}= ... =s_{n-1}^{s_n}$ and $n>4$ then $p|s_i$ $\implies$ $p|s_j$ for $i,j\in$ {$1,2,..n-1$} also for any prime $p$ dividing $a_i$ we have $s_2V_p(s_1)=s_3V_p(s_2)= ..= s_{n-2}V_p(s_{n-1})=s_{n-1}V_p(s_n)$ $\implies$ $\frac{V_p(s_i)}{V_q(s_i)}$ is constant for all $i\in$ {$1,2,..n-1$} and any prime divisors $p $ and $q$ of $s_1$. Since $\frac{V_p(s_i)}{V_q(s_i)}$ is constant , each $s_i$ must be a perfect power of some integer. (This is true since exponent of primes of $s_i$ are in a fixed ratio) Now let $s_i=a^{b_i}$ for all $i\in$ {$1,2,..n-1$}. $\implies$$b_1a^{b_2}= .. =b_{n-4}a^{b_{n-3}}=b_{n-3}a^{b_{n-2}}=b_{n-2}a^{b_{n-1}}=b_{n-1}s_n$ For simplicity let $c_1=b_{n-4} , c_2=b_{n-3} , c_3=b_{n-2} , c_4=b_{n-1}$ We will prove that $c_{1}a^{c_2}=c_{2}a^{c_{3}}=c_{3}a^{c_{4}}=c_{4}s_n$ is not possible. Case 1: $c_2>c_1$ $c_{1}a^{c_2}=c_{2}a^{c_{3}}$$\implies$ $a^{c_2}>a^{c_3}$$\implies$ $c_2>c_3$ also $c_{2}a^{c_{3}}=c_{3}a^{c_{4}}$$\implies$ $c_3>c_4$$\implies$$\frac{c_2}{c_3}$$=a^{c_4-c_3}$$\implies$$ c_3|c_2$ also $\frac{c_2}{c_1}$$=a^{c_2-c_3}$ since $c_3|c_2$ we have $c_3<$$\frac{c_2}{2}$$\implies$ $\frac{c_2}{c_1}$$ > $$a^{c_2/2}$ which is only possible if $(a,c_2,c_1)=(2,2,1),(2,3,1),(2,4,1)$. Now for $(a,c_2,c_1)=(2,2,1),(2,3,1)$,$(c_1,c_2,c_3,c_4)=(1,2,1,2),(1,3,log_2(8/3),idk)$,Both of which are contradiction. But $(a,c_2,c_1)=(2,4,1)$ gives the desired result. Case 2:$c_2<c_1$ $c_{1}a^{c_2}=c_{2}a^{c_{3}}$$\implies$ $a^{c_2}<a^{c_3}$$\implies$ $c_2<c_3$ also $c_{2}a^{c_{3}}=c_{3}a^{c_{4}}$$\implies$ $c_3>c_4$ Now we prove that $c_4|c_3$ , if not then there exist a prime $P$ such that $V_P(c_4)>V_P(c_3)$ but $c_4s_n=c_3a^{c_4}$$\implies$$P$ divides a. Let $V_P(a)=m , V_P(c_4)=l$ .Note that $c_3=c_2a^{c_3-c_4}$$\implies$$V_P(c_3)>(c_3-c_4)m$ and since $l>V_P(c_3)$ ,we have $V_P(c_3)|c_3,c_4$$\implies$ $V_P(c_3)>P^{V_P(c_3)}$$\frac{c_4-c_3}{P^{V_P(c_3)}}m$$\implies$$V_P(c_3)>P^{V_P(c_3)}$ which is a contradiction. Hence $c_4|c_3$ now from $\frac{c_3}{c_2}$$=a^{c_3-c_4}$ we will get $\frac{c_3}{c_2}$$ > $$a^{c_3/2}$ which implies $(a,c_3,c_2)=(2,2,1),(2,3,1),(2,4,1)$ which would give contradiction as $(c_1,c_2,c_3,c_4)=(2,1,2,1),(4,1,3,log_2(8/3)),(2,1,4,4)$ for $(a,c_3,c_2)=(2,2,1),(2,3,1),(2,4,1)$ respectively ,all of which are contradiction. Hence $s_{n-3}=2,s_{n-2}=16,s_{n-1}=4$$\implies$$s_1^{s_2}=s_2^{s_3}= ... =s_{n-1}^{s_n}=2^{16}$ $\implies$$s_n=8,s_{n-4}=2^8$ Note that $s_{n-5}$ does not exist as if it did then $s_{n-5}^{2^8}=2^{16}$ which would be a contradiction. Hence $n=5$ and the only solution is $(s_1,s_2,s_3,s_4,s_5)=(2^8,2,16,4,8)$. Initially I did not checked the case for $(a,c_2,c_1)=(2,4,1)$ and fake solved that $n=4$
29.06.2023 21:50
Let $s_i=c^{a_i}$ where $c\neq1$ for $i\leq n-1$. Then, $a_1c^{a_2}=a_2c^{a_3}=\ldots=a_{n-2}c^{a_{n-1}}$, so $a_i=xc^{b_i}$ for $i\leq n-2$. Therefore, we get $b_1+xc^{b_2}=b_2+xc^{b_3}=\ldots=b_{n-3}+xc^{b_{n-2}}=N$. Let $j$ be the largest number such that $N\geq xc^j$. Since the numbers are distinct, we have $b_1\neq b_2\neq\ldots\neq b_{n-2}$, so at least $n-5$ of the $b_i$ for $i\geq2$ satisfy $N-xc^{b_i}=b_{i-1}\geq xc^{j-1}(c-1)$ so $xc^{n-6+xc^{j-1}(c-1)}\leq N<xc^{j+1}$. Solving gives $n-6+xc^{j-1}(c-1)<j+1$. Since $c>1$, we get $$j+1>n-6+xc^{j-1}(c-1)\geq n-6+2^{j-1},$$or $$n<j+1-2^{j-1}+6\leq7.$$Therefore, $n\leq6$. If equality holds, then $c=2$ and $x=1$, so $a_i$ is a power of $2$. Therefore, $s_i$ must be a power of $2$ for all $i\leq n$, which gives a contradiction after the same steps. Therefore, $\boxed{n=5}$. A construction for $n=5$ is given by $256^2=2^{16}=16^4=4^8=65536$.
30.06.2023 05:27
The answer is $5$; construction is $256^2=2^{16}=16^4=4^8$. Observe that for any $i<n$ and prime $p$, we have $\tfrac{\nu_p(s_i)}{\nu_p(s_1)}=\tfrac{s_{i+1}}{s_{2}}$, so for any $i$, $s_i$ is some rational power of $s_1$. This implies that there exists some natural number $P$ such that $s_i=P^{a_i}$ for all $i$, where $a_i$ is a positive integer. The equation then becomes $$a_1P^{a_2}=a_2P^{a_3}=\cdots=a_{n-1}P^{a_n}.$$But then for any $i<j<n$, the ratio $\tfrac{a_i}{a_j}$ is a power of $P$, hence we can let $a_i=cP^{b_i}$ for all $i<n$, where $c$ is a (fixed) natural number. The equation then becomes $$b_1+cP^{b_2}=b_2+cP^{b_3}=\cdots=b_{n-2}+cP^{b_{n-1}}=b_{n-1}+a_n.$$ The key claim here is that for $2 \leq i \leq n-1$ we must have $b_i \leq 2$. Indeed, by taking $i$ such that $b_i$ is maximal, we find that $$b_{i-1}+cP^{b_i}=b_i+cP^{b_{i+1}} \implies b_{i-1}=b_i-c(P^{b_i}-P^{b_{i+1}})\leq b_i-cP^{b_i-1}\leq b_i-2^{b_i-1},$$but if $b_i \geq 3$ then this final value is negative. Since we need $a_i$ to be a positive integer, we have $cP^{b_{i-1}} \geq 1$, so $cP^{b_i-1}=cP^{b_{i-1}}\cdot P^{b_i-b_{i-1}-1}\geq P^{b_i-b_{i-1}-1}$, so $b_{i-1} \leq b_i-P^{b_i-b_{i-1}-1} \implies P^{b_i+(-b_{i-1})-1} \leq b_i+(-b_{i-1})$, but this can clearly be checked to be impossible (for $b_i \geq 3$). This finishes the problem, since the $b_i$ must be distinct, so between $2$ and $n-1$ inclusive there are at most $3$ of them. This misses $b_1$ and also $a_n$ (since $b_n$ doesn't exist), so $n=5$ is maximal. $\blacksquare$
01.07.2023 19:00
My problem! Original problem statement wrote: Determine the longest possible length of a sequence of distinct positive integers $s_1$, $s_2$, $\ldots$, $s_n$ for which \[s_1^{s_2} = s_2^{s_3} = \ldots = \left(s_{n-1}\right)^{s_n}.\]