2
$\begingroup$

Consider a sequence of $N$ positive integers containing n distinct integers. If $N \geq 2^n$, show that there is a consecutive block of integers whose product is a perfect square. Is this inequality the best possible?

What is the trick to solve this problem?

2 Answers 2

5

Let $A_j(k)$ be the parity (even or odd) of the number of times the $j$'th distinct integer occurs in the first $k$ members of the sequence. There are $2^n$ possibilities...

2

To show it's best possible, think about the following sequence where you can, for example, take $a,b,c\dots$ to be distinct primes:

$a$;
$a,b,a$;
$a,b,a,c,a,b,a$;
$a,b,a,c,a,b,a,d,a,b,a,c,a,b,a$;
etc.