3
$\begingroup$

Let $A$ be a set of $n$ positive integers. Show that every sequence of $2^n$ numbers taken from $A$ contains a consecutive block of numbers whose product is square.(For instance, {2,5,3,2,5,2,3,5} contains the block 5,3,2,5,2,3 .)

I think this has something to do with the pigeon-hole principle but apart from that I have no idea how to proceed any further.

Any hint guys?

Thank You

2 Answers 2

3

Hint: You have a list of $2^n$ vectors of length $n$ over $\mathbb{Z}_2$. Show that there is a consecutive block of vectors that sum to zero.

  • 0
    @zyx, I thought you were asking why $\le n$ would always be enough. Even if a smaller space can sometimes work, it is easier always to use the same size and just pad with zeroes if not all dimensions are needed. It's just an existence proof we're after, after all.2011-10-30
0

First I'm sorry for bad English. But there is a solution.

Define sets for i = 1 to 2^n :

M(i) = {x ; x is number with odd occurence in subsequence from position 1 to i} M(0) = {}

For every i M(i) is subset of A.

{M(0), M(1), …, M(2^n)} is set of 2^n + 1 set. But number of all subsets of A i 2^n. So there must exists j and k that M(j) = M(k). Subsequence from position j + 1 to position k is then a perfect square.