FROM THE FIRST 30 POSITIVE INTEGERS, WHAT IS THE MAXIMUM NUMBER OF...

5. From the first 30 positive integers, what is the maximum number of integers that

can be chosen such that the product is a perfect square?

【Solution 1】

We first determine the prime factorization of the first 30 positive integers.

1 2 3 2×2 5 2×3

7 2×2×2 3×3 2×5 11 2×2×3

13 2×7 3×5 2×2×2×2 17 2×3×3

19 2×2×5 3×7 2×11 23 2×2×2×3

5×5 2×13 3×3×3 2×2×7 29 2×3×5

The product of all 30 numbers is 2

²⁶

× 3

¹⁴

× × × 5

⁷

7

⁴

11

²

× 13

²

× × × × 17 19 23 29 . We

must leave out 17, 19, 23 and 29, but this is still not the square of an integer until we

also leave out 5. It follows that we can choose at most 25 numbers.

【Solution 2】

To count the number of 2’s in the prime factorization of 30!, we collect a 2 from

every second number, a second 2 from every fourth number, a third 2 from every

eighth number, and a fourth 2 from every sixteenth number. The total is 15+7+3+1

     

+ + = + +

=26. Similarly, the total number of 3’s is given by 30 30 30

10 3 1

     

     

3 9 27

 

   

+ = + =

  =

6 1 7

= 14 , the number of 5’s is 30 30

7 4

   

  .

    and the number of 7’s is 30

5 25

It is easy to see that the numbers of 11’s and 13’s are both 2, while the numbers of

17’s, 19’s, 23’s and 29’s are all 1. We can choose 25 numbers, all but 5, 17, 19, 23

and 29.

ANS: 25