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
    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$?2011-10-03
  • 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
    All: Please comment, whether you think this is giving too much help for a HW problem?2011-10-03
  • 0
    Seems like a perfectly reasonable answer to me.2011-10-03
  • 0
    I don't really understand how 16 is the number of pigeonholes.2011-10-03
  • 0
    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$.2011-10-03
  • 0
    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.2011-10-03
  • 0
    @user952949. It is not a stupid question at all, because it is the key. I described 16 pigeons and 16 holes. What happens, if all the pigeons end up in different holes? What happens, if two or more pigeons go to the same hole?2011-10-03
  • 0
    Oh, okay now I think I got it. So when two products are in the same hole, the powers of this final product are all even. Hence it proves that there is always a product which forms even powers.2011-10-05
  • 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