2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Please include in your post your attempt at solving the problem. Otherwise, your question will likely be closed. $\endgroup$ – Aaron Hendrickson Jun 10 at 21:13
  • 1
    $\begingroup$ Hint: consider sets of the form $\{xy\mid y\in\{1,4,9,16,25,36\},\;xy\leq 36\}$ for square free natural numbers $x$. $\endgroup$ – Don Thousand Jun 10 at 21:14
  • $\begingroup$ This doesn't really seem like a contest problem. If nothing else you can simply check for each $a$ which integers $b; b> a$ in $\{1,2,\ldots, 36\}$ are such that $ab$ is a perfect square, with a few shortcuts along the way: If $a$ is prime then $b$ must be of the form $c^2a$; if $a$ is not prime then write $a=d^2e$ where $d^2$ is the largest square dividing $a$; then $b$ must be of the form $ef^2$ for some other square $f$.... $\endgroup$ – Mike Jun 10 at 21:48
  • $\begingroup$ So $6$ gives $6=1^2 \times 6$ so $e=6$ and $c^2=1^2$, so the pairs where $6$ is the smallest integer is $(6,24)$. $\endgroup$ – Mike Jun 10 at 21:50
  • $\begingroup$ OR rather, for each integer $c$ in $\{1,2,\ldots, 36\}$, check the number of ways you can get $c^2$. For example, $c=8$, so $c^2=64=2 \times 32 =4 \times 16$. This is more direct. $\endgroup$ – Mike Jun 10 at 22:03
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ah, I see my answer here is essentially the same as Aaron's, just more tersely presented. $\endgroup$ – Barry Cipra Jun 10 at 23:08
  • $\begingroup$ This explanation is helpful . Thank you. $\endgroup$ – LxSquid Official Jun 16 at 16:14
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This explanation is helpful . Thank you. $\endgroup$ – LxSquid Official Jun 16 at 16:14
1
$\begingroup$

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.

$\endgroup$

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.