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$

$\endgroup$
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\}$

$\endgroup$
  • 1
    $\begingroup$ I had the same idea. I looked up the numbers on OEIS: A005117 $\endgroup$ – Jaap Scherphuis Dec 5 '19 at 15:04
  • $\begingroup$ @JaapScherphuis Aha, I actually wrote this out by hand, really should have checked OEIS. $\endgroup$ – hexomino Dec 5 '19 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 '19 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 '19 at 10:07

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.