Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem (from Putnam and Beyond pg. 11) is:

Given a set $M$ of 1985 distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements whose product is the fourth power of an integer.

Solution is:

We show more generally that if the prime divisors of elements in M are among the prime numbers $p_1,p_2,\ldots,p_n$ and $M$ has at least $3 \cdot 2^{n} + 1$ elements, then it contains a subset of four distinct elements whose product is a fourth power. To each element m in M we associate an $n$-tuple $(x_1,x_2,\ldots,x_n)$, where $x_i$ is 0 if the exponent of $p_i$ in the prime factorization of $m$ is even, and 1 otherwise. These $n$-tuples are the “objects.’’ The “boxes’’ are the $2^{n}$ possible choices of 0’s and 1’s. Hence, by the pigeonhole principle, every subset of $2^{n}+1$ elements of $M$ contains two distinct elements with the same associated $n$-tuple, and the product of these two elements is then a square. We can repeatedly take aside such pairs and replace them with two of the remaining numbers. From the set $M$, which has at least $3 \cdot 2^{n}+1$ elements, we can select $2^{n}+1$ such pairs or more. Consider the $2^{n}+1$ numbers that are products of the two elements of each pair

My question: The crux of the pigeonhole problem I already understand however I do not understand why there necessary be $3 \cdot 2^{n}+1$ elements. If the purpose is to find $2^{n}+1$ pairs where each pair is a square (and product of two numbers) [to repeat the pigeonhole argument], then really shouldn't the number of elements be assumed is $2(2^{n}+1)$ rather than $3 \cdot 2^{n}+1$? I feel that my reasoning is correct but at the same time missing something as it differs from the solution.

Thanks.

share|improve this question
    
If this is a contest problem, you should give the source and the source of the solution. –  Mark Bennet May 25 '12 at 15:34
    
Sounds like a problem from the year 1985. I think I have seen essentially the same problem a few years prior to that. So I don't think this is an ongoing contest problem, @Mark. –  Jyrki Lahtonen May 25 '12 at 15:36
    
Added: from Putnam and Beyond. –  Mat.S May 25 '12 at 15:37

2 Answers 2

up vote 2 down vote accepted

The number of pairs you need is $2^n+1$, and these contain $2(2^n+1)$ elements. But to find the last pair you need to use the pigeonhole principle on the last $2^n+1$ elements, and when you have taken that pair away you will have $2^n-1$ discarded elements.

$2(2^n+1)$ selected elements plus $2^n-1$ discarded elements = ...

IMO 1995 problem 4. This solution is given in Murray Klamkin "International Mathematical Olympiads 1978-85"

share|improve this answer
    
Ah, thanks for clarifying this oversight. –  Mat.S May 25 '12 at 16:01

Everytime you apply the pigeon hole principle, you remove a pair of numbers. To be guaranteed to find the last matching pair, you must have $2^n+1$ number remaining at that point. But you have already removed $2^n$ pairs, so...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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