# Pigeonhole Technical Problem

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.

• 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

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"

• 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...