There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or all the numbers can be nine).
Prove that we can always chose consecutive numbers from these 16 numbers such that their product forms a square number. The conditions are that we must chose at least one number, and the numbers chosen must be consecutive (i.e. next to each other in the string of 16 numbers).
I think I should use the Pigeonhole principle here. Here are a few ideas I had about approaching this:
There are a total of $10^{16}$ ways of forming a string of length 16, with numbers from 0-9. These can possibly be the pigeonholes.
I was thinking the pigeons should be something like the number of strings which have consecutive numbers such that their product form a square number.
The largest possible square number we can have is when all 16 digits are 9, and we pick all 16 digits (we can pick less than this, for example 9 and 9). Hence, we will form the square number $9^{16}= 1853020188851841 (= 43046721^2)$.
We know that every natural number has a unique prime factorisation. Hence all square numbers have unique factorisations. Between $0$-$9$, we have $2$, $3$, $5$, and $7$ as prime numbers. From these prime numbers, we can form any square number.
From any natural number $x$, we can get to a square number, by taking the prime factorisation of $x$, and turning any odd powers into even powers.
Ok, I pretty much threw in the kitchen sink. Can someone please give me a small pointer on how to form the pigeons in this problem. A hint would do.