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.