5
$\begingroup$

There are 100 cards on a table numbered 1,2,...,100. What is the maximum number of cards, which can be selected such that no two cards have a product, which is a perfect square?

Example: you cannot choose the cards with number 27 and 48, as $27*48=81*16=36^2$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

The maximum is

61

Reasoning

We cannot choose two numbers whose square-free part is the same but any two numbers which have a square-free part which is different won't produce a square as a product. This means we could just choose all the numbers which are completely square-free (i.e, have no factor which is a square). This results in the following set
$\{ 1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,82,83,85,86,87,89,91,93, 94,95,97\}$

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I had the same idea. I looked up the numbers on OEIS: A005117 $\endgroup$
    – Jaap Scherphuis
    Dec 5, 2019 at 15:04
  • $\begingroup$ @JaapScherphuis Aha, I actually wrote this out by hand, really should have checked OEIS. $\endgroup$
    – hexomino
    Dec 5, 2019 at 15:05
  • $\begingroup$ Is this a unique answer? Can we replace 1 with any perfect square like 4 etc., to get another set containing 61 elements that will serve as the answer? $\endgroup$
    – ContraOpposite
    Dec 5, 2019 at 22:45
  • 1
    $\begingroup$ @ContraOpposite Yes, we could replace $1$ with any perfect square. Also, we could replace $2$ with any number of the form $2n^2$, etc. Overall, I think this means there are $10 \times 7 \times 5 \times 4^2 \times 3^3 \times 2^8 = 38707200$ different $61$-element solutions. $\endgroup$
    – hexomino
    Dec 6, 2019 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.