Prove that in every $16$-digit number there is a chain of one or more consecutive digits such that the product of those digits is a perfect square. For example, if the original number is $7862328578632785$ we can take the digits $6$, $2$ and $3$ whose product is $6^2$ (note that these appear consecutively in the number).
Problem
Source: Mathematics Regional Olympiad of Mexico West 2021 P2
Tags: number theory, Perfect Square
09.09.2022 23:32
I feel like this can be done by severe case study (or perhaps bounding the number of perfect squares that can be formed and the number of possibilities of numbers containing no 2 consecutive numbers or something) but I can't really think of anything else... $2,3,5,6,7,8$ are the only digits that can be used and combinations such as ${2,8}, {2,3,6}$ etc give perfect squares. Bump?
12.09.2022 21:00
Consider the sequence with $16$ digits $s_1,s_2,s_3\dots s_{15},s_{16}$. Denote $P_k=s_1\cdot s_2\cdot...\cdot s_{k-1}\cdot s_k;\;k\in\{1,2,\dots,15,16\}$. If the sequence contains a digit $s_k\in\{0,1,4,9\}$, the problem is solved: the sequence which contains only the digit $s_k$ is a perfect square. Assume all digits $s_k\in\{2,3,5,6,7,8\};\;k\in\{1,2,\dots,15,16\}$. $6=2\cdot3;\;8=2^3$. Results: $\exists x_k,y_k,z_k,t_k\in\mathbb{N}\cup\{0\}$ such that $P_k=2^{x_k}\cdot3^{y_k}\cdot5^{z_k}\cdot7^{t_k}$. Denote $a_k=x_k\pmod{2};\;b_k=y_k\pmod{2};\;c_k=z_k\pmod{2};\;d_k=t_k\pmod{2}$, hence $a_k,b_k,c_k,d_k\in\{0,1\}$. If exists $k\in\{1,2,\dots,15,16\}$ such that $(a_k,b_k,c_k,d_k)=(0,0,0,0)$, then $P_k$ is perfect square. Assume $(a_k,b_k,c_k,d_k)\ne(0,0,0,0);\;\forall k\in\{1,2,\dots,15,16\}$. The number of possible $4$-tuples $(a_k,b_k,c_k,d_k)\ne(0,0,0,0)$ is $2^4-1=15$. Results: $\exists m,n\{1,2,\dots,15,16\},\;m<n$ such that $(a_m,b_m,c_m,d_m)=(a_n,b_n,c_n,d_n)\Longrightarrow$ $\Longrightarrow P_n=P_m\cdot 2^p\cdot 3^q\cdot 5^u\cdot 7^v$, where $p,q,u,v$ are even non-negative integers (not all zero), hence $s_{m+1}\cdot s_{m+2}\cdot\dots s_{n-1}\cdot s_n=\dfrac{P_n}{P_m}=2^p\cdot 3^q\cdot 5^u\cdot 7^v$ is a perfect square.