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

Improve this question
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Length $\leq n$? $\endgroup$ – zyx Oct 30 '11 at 2:12
  • $\begingroup$ @zyx, yes because we can pretend wlog that the numbers in $A$ are distinct primes. Then the criterion is just that the consecutive block must contain an even number of instances of each element. $\endgroup$ – hmakholm left over Monica Oct 30 '11 at 6:59
  • $\begingroup$ @Henning, that observation was the point of my question. All numbers relatively prime is the worst case. In the easier case such as powers of one prime, the mod 2 vector space is of smaller dimension so one can either improve the statement of the problem (one does not quite need 2^n numbers from A but 2^(dimension of the mod 2 space for A), or the wording of the answer should be modified slightly. Assuming that you and I and Yuval are discussing the same vector space... $\endgroup$ – zyx Oct 30 '11 at 7:07
  • $\begingroup$ @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. $\endgroup$ – hmakholm left over Monica Oct 30 '11 at 7:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.