5. The numbers $1,2,3, \ldots, 16$ are written on slips of paper, one number per slip. Kosta, without looking, sequentially draws one slip at a time, until the product of the numbers written on any two of the drawn slips is a perfect square. What is the maximum number of slips Kosta can draw without the product of any two numbers written on the drawn slips being a perfect square?
Solution. The prime numbers less than 16 are 2, 3, 5, 7, 11, and 13. Clearly, the product of any two of them is not a perfect square. If we add the number 1 to these numbers, then the product of any two numbers from the set \{1, 2, 3, 5, 7, 11, 13\} is not a perfect square. Furthermore, the numbers less than 16 that can be written as the product of two different prime numbers are \(6=2 \cdot 3\), \(10=2 \cdot 5\), \(14=2 \cdot 7\), and \(15=3 \cdot 5\). Clearly, the product of any two of these numbers, as well as the product of one number from the set \{1, 2, 3, 5, 7, 11, 13\} and one number from the set \{6, 10, 14, 15\}, is not a perfect square. Therefore, Costa can draw at most \(7+4=11\) numbers without the product of any two of the drawn numbers being a perfect square.

Finally, if Costa further draws any of the numbers 4, 8, 9, 12, or 16, the condition is violated because

$$
1 \cdot 4=2^{2}, 2 \cdot 8=4^{2}, 1 \cdot 9=3^{2}, 3 \cdot 12=6^{2} \text { and } 1 \cdot 16=4^{2}
$$

## VIII Section