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 '17 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$ – Trixie Wolf Apr 29 '17 at 13:01

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.

| cite | improve this answer | |
  • $\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 '17 at 3:01

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.