Proof that for any $16$ digit number there is at least one sequence of $1$ or more digits which its product is a perfect square

Question

I came across this problem where one is asked to proof that, for any $16$ digit number there is at least a sequence of $1$ or more digits which its product is a perfect square.

For example, in the number

$$4,562,348,973,245,984$$

The product of $$6·2·3=36$$ and $$\sqrt{36}=6$$ (third, fourth and fifth digit) is a perfect square.

I've been trying for a while now but haven't been able to come up with anything interesting.

I tried to approach the problem from a pigeon hole perspective, trying to prove that the number of perfect squares that can be made with the product of $1$ to $n$ digits, were each digit ranges from $0$ to $9$ is bigger or equal that the amount of perfect squares a $16$ digit number can hold by the number of $16$ digit numbers. Although I think this approach should work, I had a lot of trouble when trying to figure out the numbers (total number of perfect squares, perfect squares a $16$ digit number can have in the terms expressed above) in order to do the calculations.

So then I took a different approach which was trying to prove that for any $16$ digit number there was at least one product of $n$ (from $1$ to $16$) digits which its square root was an integer, but I don't know how to formulate this idea.

Obviously brute forcing it by hand its not an option as numbers and combinations are quite big.

How can I prove the statement to be true?

And on a more general topic,what goes through your mind when having to prove something? Which should be the steps taken?

As far as I see it there are some steps which are unavoidable:

1- Come out with some effects/requisites that derive from the assumption that the statement you want to prove ( the cause) is true or false.

2- Mathematicaly formulate them.

3- See if the expected effects/requisites are true and from that conclude that tge cause/the original statement has also to be true.

Answer 1

We can assume that the number does not have any digit equal to $0$. For if it has, then the statement is obvious. Note that the prime factors of the remaining digits are $2$, $3$, $5$ and $7$.

Now, for a given number whose prime factors are among ${2,3,5,7}$ define the function $$f(2^{a_2}3^{a_3}5^{a_5}7^{a_7})=(g(a_2),g(a_3),g(a_5),g(a_7))$$

Where $g(k)$ is $1$ if $k$ is odd and $0$ if $k$ is even. Consider the image as a vector of $\Bbb Z_2^4$.

This function takes $2^4=16$ possible values.

Now, lets write $p(n,m)$ for the product of the digits from $n$th to $m$th. Note that $f$ are defined for this values since their prime factors are always among $2,3,5$ and $7$. If some of the values $$f(p(1,m))$$ is $(0,0,0,0)$ then $p(1,m)$ is a square. If not, the set $\{f(p(1,1)),f(p(1,2)),\ldots,f(p(1,16))\}$ has at most $15$ different elements. So there are two equal values, say $p(1,n)$ and $p(1,m)$. Then $$f(p(n+1,m))=f\left(\frac{p(1,m)}{p(1,n)}\right)=f(p(1,m))-f(p(1,n))=(0,0,0,0)$$ so $p(n+1,m)$ is a square, q.e.d.

Answer 2

First, if any digit is a zero, it in itself is a square. Thus, let’s assume that there are no zero digits.

Now look at all products of digits starting from the first digit to either itself or some later digit. There are $16$ of those products: if the digits are $a_1,a_2,\ldots,a_{16}$, we are here looking at the products: $p_1=a_1, p_2=a_1a_2, p_3=a_1a_2a_3,\ldots,p_{16}=a_1a_2\cdots a_{16}$. Notice all those products have, as prime factors, only $2$,$3$,$5$ and $7$.

Recall that a number is a square if all prime factors of it have even powers. Thus, let’s watch the parities of the powers of $2,3,5,7$ (in that order) in $p_1,p_2,\ldots,p_{16}$. Obviously, each of them can be “odd” or “even” - two choices, so all four parities give you $2^4=16$ choices/quadruplets for the four parities. For example: (even, even, even, even), (even, even, even, odd), ..., (odd, odd, odd, odd).

Now, there are only two possibilities:

• All $p_1,p_2,\ldots,p_{16}$ have different (quadruplets of) parities. Thus, one of them (say $p_i$) must have the parities (even, even, even, even). Thus, $p_i=a_1a_2\cdots a_i$ is a square.
• Two of $p$’s have the same (quadruplets of) parities. If, say, $p_i$ and $p_j$ have the same parities, for $i<j$, then $\frac{p_j}{p_i}=a_{i+1}a_{i+2}\cdots a_j$ is a square.