# $16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

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.

-
Just wondering, so if we had a $1$ in there, could we just choose it and say we're done? Or a $0$, $4$ or $9$? – Josh Chen Oct 3 '11 at 7:59
@Josh: Yes, as long as we pick at least 1 number, we are done. So we can indeed just pick 1, or 4, or 9 and we will be done. – user952949 Oct 3 '11 at 8:02

If the sequence contains a 0 then we are done, so assume that's not the case (1,4 and 9 can also be ignored, and the distinction between 2 and 8 can also be ignored, but let's forget that).

As you observed only the primes 2,3,5 and 7 can occur as factors. We want a partial string such that all these four primes occur as factors with an even multiplicity. Hmm. $2^4=16$. Getting warmer!

Let $n_1,n_2,\ldots, n_{16}$ be the numbers.

Hint #1: There shall be 16 pigeonholes. A number of the form $2^a3^b5^c7^d$ goes to one of the 16 holes according to which (if any) of the exponents $a,b,c,d$ are even and which are odd. Two choices (even vs. odd) for all four exponents, so altogether 16 holes.

Hint #2: The pigeons shall be the products of the initial sequences $p_k=n_1 n_2\cdots n_k$, for $k=1,2,\ldots,16$.

Turn up the thermostat!! There are a couple of observations that you need to make :-)

==============================

Edit: May be the penny didn't drop?

Hint #3: If one of these pigeons falls into the hole, where $a,b,c,d$ are all even, then we are done. If not, then there will be only 15 pigeon holes available to our initial products. Therefore two of them, say $p_k$ and $p_\ell, k<\ell$ will go to the same hole. What can you say about $p_\ell/p_k$?

-
All: Please comment, whether you think this is giving too much help for a HW problem? – Jyrki Lahtonen Oct 3 '11 at 8:11
Seems like a perfectly reasonable answer to me. – Brian M. Scott Oct 3 '11 at 8:21
I don't really understand how 16 is the number of pigeonholes. – user952949 Oct 3 '11 at 9:05
The holes are EEEE, EEEO, EEOO, ..., OOOE, OOOO, where the first letter tells whether the exponent of $2$ is Even or Odd. The second letter says the same thing about the exponent of $3$, the third letter is about $5$, and the last about $7$. – Jyrki Lahtonen Oct 3 '11 at 9:08
I'm sorry if this is a stupid question, but when we say that 16 is the total number of combinations of the 4 prime numbers we can have, we are including in that odd powers as well as even powers. So then when we get the pigeons, then say that the number of pigeons is greater than 16, then aren't we also including all the sequences with odd powers? That does not help our proof. It does not show that the number of pigeons is only greater than even power strings. – user952949 Oct 3 '11 at 10:08