Question: Assume you choose any $48$ positive integers so that the number of different prime factors of all those numbers is $10$. Prove or disprove there exists a set of four numbers out of the $48$ positive integers of which product is a perfect square.

I think that it uses pigeon hole, but I couldn't make a progress.

  • $\begingroup$ why is everyone downvoting this? $\endgroup$
    – amakelov
    Apr 29, 2017 at 5:09
  • $\begingroup$ Unless I misread the question originally (which is very likely), the original wording of the question read as though Kay were asking, "Prove or disprove that there exist four numbers out of { 1, 2, ... 48 } which multiply to form a perfect square." People are downvoting it because they misunderstand the question. (I'm removing my downvote now that I understand it.) $\endgroup$ Apr 29, 2017 at 13:01

1 Answer 1


It can be done.

Let the 10 prime factors be $p_1,\ldots,p_{10}$, then every number among the set $S$ of 48 can be written in the form $p_1^{d_1}\ldots p_{10}^{d_{10}}$. Now there are 1024 possibilities for $(d_1,\ldots,d_{10})$ modulo 2.

So in particular, if we look at all products $ab$ for $a,b\in S,a\neq b$, there will be ${48\choose 2} = 1128>1024$ such products, and the corresponding vectors $(d_1,\ldots,d_{10})$ for some two products $a_1b_1,a_2b_2$ will be the same modulo 2, meaning that $a_1b_1a_2b_2$ is a perfect square.

This is all nice and well if the numbers $a_1,b_1,a_2,b_2$ are all distinct, but if they're not we need to do some more work. Namely, the only way they can fail to be distinct is if $\{a_1,b_1\}\cap\{a_2,b_2\}$ has size 1. In this case, if WLOG $b_1=a_2=c$, we get that $a_1c^2b_2$ is a perfect square, which means that $a_1b_2$ is a perfect square.

Now comes the key step: we throw away $a_1b_2$ and repeat the argument! Since there will now be ${46\choose 2} = 1035 > 1024$ pairs, everything works, and either we're in the easy case (in which we win immediately), or we're in the bad case where we get some $a_1',b_2'\in S-\{a_1,b_2\}$ such that $a_1'b_2'$ is a perfect square. Now, combine all 4 of $a_1,b_2,a_1',b_2'$ to finish the proof.

  • $\begingroup$ Understood. Thanks a lot. I have another problem that is similar. I would appreciate if you can tackle that one too. I'll post it in a few mins. $\endgroup$
    – Kay K.
    Apr 29, 2017 at 3:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .