jmc

Question

Each of the integers 1, 2, 3, , 16 is written on a separate slip of paper and these slips are placed in a pile. Jillian will randomly draw slips from the pile without replacement and will continue drawing until two of the numbers she has drawn from the pile have a product that is a perfect square. What is the maximum number of slips that Jillian can draw without obtaining a product that is a perfect square?

Accepted Answer

Recall that an integer is called square-free if the only exponent which appears in the prime factorization of the integer is

1.

For example,

2 \cdot 3 \cdot 11

is square-free, but

7^{3} \cdot 13

and

2^{2} \cdot 3

are not. We define the "square-free part" of a positive integer which is not a perfect square to be largest square-free factor of the integer. For example, the square-free part of

18

is

6,

and the square-free part of

54

is

6.

Perfect squares have a square-free part of

1.

Notice that two positive integers multiply to give a perfect square if and only if either their square free parts are equal or the integers are both perfect squares. Therefore, if we look at the square free parts of the integers between

1

and

16,

the maximum number of slips that Jillian can draw is the number of distinct square free parts that appear. The table below (broken into two lines) shows the square-free parts of the integers between

1

and

16.

1122334155667782

9110101111123131314141515161

Jillian may draw the slips marked

5,

6,

7,

10,

11,

13,

14,

and

15,

as well as one from each of the sets

{1, 4, 9, 16},

{2, 8},

and

{3, 12}

for a total of

11

slips.