For how many two-element subsets $\{a, b\}$ of the set $\{1, 2, 3, 4, 5, 6, \dots , 36\}$ is the product $ab$ a perfect square?

Question

Problem:

For how many two-element subsets $\{a, b\}$ of the set $\{1, 2, 3, 4, 5, 6, \dots , 36\}$ is the product $ab$ a perfect square?

Note:

The numbers $a$ and $b$ are distinct, so the $a$ and $b$ must be different integers from the set of numbers $1 - 36$.

Reiteration:

Using two integers selected from the number group, $1-36$, how many combinations are possible so that the product of the two numbers selected is a perfect square.

Attempt:

First list out the square numbers between 1-36 (inclusive):

1, 4, 9, 16, 25, 36.

NOTE: The square number “1” does not work because a and b need to be distinct.

Rewrite the numbers paired with the number “1” so that it is in the format {a, b}.

(4, 1) (9, 1) (16, 1) (25, 1) (36, 1)

Next, since the number “16” for example, it can be broken down into 4•4 or 8•2, the subset {8, 2} also works.

4 : 2•2 (Note: 2•2 does not work because a and b need to be distinct) 16 : 4•4 or 8•2 (Note: 4•4 does not work because a and b need to be distinct) 36 : 2•18 or 3•12 or 4•9

Currently, we have found 9 solutions.

Issue:

I currently found 9 out of the total number of solutions that satisfy this problem. But, I have ran into an issue : What is the most efficient way to organize your solutions and find other combinations?

Attempt Continued:

I then continued to list out the combinations but started with the sets with “1” in the front and then 2, then 3, then 4, etc.

Subsets which start with “1”:

{1, 4} {1, 9} {1, 16} {1, 25} {1, 36}

Subsets which start with “2”:

{2, 8} {2, 18} {2, 32}

Subsets which start with “3”:

{3, 12} {3, 27}

Subsets which start with “4”:

{4, 9} {4, 16} {4, 25} {4, 36}

Subsets which start with “5”:

{5, 20}

Subsets which start with “6”:

{6, 24}

Subsets which start with “7”:

{7, 28}

Subsets which start with “8”:

{8, 18} {8, 16}

Conclusion:

The list keeps going on. The correct answer for this question is 27. If you carefully calculate and list out the subsets, you can get the answer.

Answer 1

The challenge here is to think of some efficient way to "see" the solution. Here's one idea, based on the OP's first step, namely isolating the squares:

Partition the integers from $1$ to $36$ into square multiples of squarefree numbers:

$$\begin{align} &\{1,4,9,16,25,36\}\\ &\{2,8,18,32\}\\ &\{3,12,27\}\\ &\{5,20\}\\ &\{6,24\}\\ &\{7,28\}\\ \end{align}$$

where we don't need to go any further because every other number belongs to a singleton. Now pairs $a$ and $b$ that multiply to a square must both come from the same set. We thus have

$${6\choose2}+{4\choose2}+{3\choose2}+{2\choose2}+{2\choose2}+{2\choose2}=15+6+3+1+1+1=27$$

pairs in all.

Answer 2

Define $f(n)$ to be $n$ divided by the largest perfect square that divides $n$; for example, $f(180) = f(6^2\cdot5)=5$ and $f(30)=30$ and $f(25)=1$. Then $ab$ is a perfect square if and only if $f(a)=f(b)$, which should make the answer easy to calculate.

Answer 3

Every number $n$ can be written as the product of a square part and a square-free part $n=a^2b$ where no perfect square besides $1$ divides $b$. One way to see this is to look at the prime factorization: if $n=\prod p_i^{k_i}$, let $\epsilon_i=1$ if $k_i$ is odd and $0$ if $k_i$ is even. Then $a=\prod p_i^{\lfloor k_i/2 \rfloor}$ and $b=\prod p_i^{\epsilon_i}$. Then $mn$ will be a perfect square if and only if the squarefree part of $m$ equals the squarefree part of $n$.

By getting rid of all the multiples of 4, 9, and 25, we see that the squarefree numbers less than 36 are

$$1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35$$

For each of these numbers, we can look at how many different square parts can go with those square-free parts to get a number less than or equal to 36. For any number greater than 9, there is at most 1 number with that square-free part: we would be $1^2b$, but then $2^2b$ would already be too big. So, for example, there aren't two numbers less than 36 that both have square-free part 11, and so no way to multiply 11 by something less than 36 to get a perfect square.

The squarefree numbers less than 9 are

$$1, 2, 3, 5, 6, 7$$

and the numbers with those square-free parts are the following sets $$\{1,4,9,16,25,36\}, \{2, 8, 18, 32\}, \{3, 12, 27\}, \{5, 20\}, \{6, 24\}, \{7, 28\}.$$

There are 6C2 ways to pick 2 numbers from the first set, 4C2 ways to pick 2 numbers from the second set, 3C2 ways to pick 2 numbers from the 3rd set, and 1 way to pick 2 numbers from each of the last 3 sets. This gives a total of $15+6+3+1+1+1=27$ different 2 element sets.

Note that we could have figured out how big each of those sets were without listing out all the elements, for example, if the square-free part of a number is 3, and $3a^2\leq 36$, then $a\leq \sqrt{26/3}$, but it is instructive to list out the full sets.