# How many perfect squares exist? [closed]

Consider a set of $1985$ positive integers not necessarily distinct. Every number in set can be written in the form $p_1^{{\alpha _1}}p_2^{{\alpha _2}} \cdots p_9^{{\alpha _9}}$ where $p_1,p_2,\ldots,p_9$ are distinct prime numbers and $\alpha_1,\alpha_2,\ldots,\alpha_9$ are non-negative integers. At least how many pairs of integers exist in this set such that their product is a perfect square?

## closed as off-topic by heropup, Shailesh, Daniel W. Farlow, JonMark Perry, Claude LeiboviciApr 14 '16 at 3:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – heropup, Shailesh, Daniel W. Farlow, JonMark Perry, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

• I'm not sure I understand the question, but isn't one pair enough? Example $p_1=2$ and $\alpha_1=2$. – Paul Irofti Apr 6 '16 at 15:47
• not necessarily distinct $\implies$ multi-set, not set. – barak manos Apr 6 '16 at 16:02

## 1 Answer

Consider the map $f\colon n\mapsto(\alpha_1\bmod 2,\ldots,\alpha_9\bmod 2)\in\{0,1\}^{9}$. For two numbers $n,m$, the product $nm$ is a perfect square iff $f(n)=f(m)$. So if $c_1,\ldots,c_{512}$ are the cardinalities of preimages of the $1024$ elements of $\{0,1\}^{9}$, then we have $$\sum{c_i\choose 2}=\frac12\sum c_i^2-\frac12\sum c_i=\frac12\sum c_i^2-\frac{1985}2$$ such pairs. The quadratic sum becomes minimal (under the restriction of $\sum c_i=1985$) if the $c_i$ are "as equal as possible", so there must be $449$ times $c_i=4$ and $63$ times $c_i=3$, leading to a minimal (and actually achievable) result of $$449\cdot{4\choose 2}+63\cdot {3\choose 2}=2883.$$

• Should the exponent be 9 instead of 10 since there is 9 primes ? – Alain Remillard Apr 6 '16 at 15:47
• @AlainRemillard Yeah, this problem initially just reminded me of a IMO 1985 problem that was about 10 primes adn old memory took over :) – Hagen von Eitzen Apr 6 '16 at 15:49
• I could have guess this problem was created in 1985 :) I had the first part right but couldn't get the last. Thanks – Alain Remillard Apr 6 '16 at 15:53
• @ Hagen von Eitzen -In 'Art and Craft of Problem Solving' it has been said that the number of such pair is 736. I cannot understand which is correct. – user322683 Apr 6 '16 at 16:56
• @ParthaGhosh 736 would mean that in a minimizing set, many numbers are not part of any pair at all, i.e.have a unique "exponent parity vector". But then some other cluster must have more than two members and moving one number from that cluster to the singleton would decrease the number of pairs, contradicting minimality. - But if you actually now have two proofs at hand that prove contradictory facts, try to dig into both until you find the mistake (there might still be a miscomputation in mine as well, but not by that much I suppose) - Maybe AaCoPS asks other, such as about disjoint pairs? – Hagen von Eitzen Apr 6 '16 at 17:43