4
$\begingroup$

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.

  • 0
    @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.2011-10-03

1 Answers 1

4

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$?

  • 0
    @user952949: Good! The ratio of those two product is also a product of consecutive entries, and it is a square, because all the primes appear in that ratio raised to an even power. I didn't want to give the game away too soon. This type of a problem is bread n' butter in, e.g. math contests, so I felt that it is better to let you sweat on it :-)2011-10-05