Product Free Subet

Clearly, $A = \{ 10, 11, 12, \ldots 100 \}$ satisfies the conditions of the question. We have $|A| = 91$ .

Suppose that $B$ is another subset that satisfies the conditions.
If $1 \in B$ then we must have $B = \{ 1 \}$ and so $|B| = 1$ . Henceforce, we assume $1 \not \in B$ .
Let $C = B \cap \{ 2, 3, 4, 5, 6, 7, 8, 9 \}$ . The goal is to map every element in $C$ to a distinct element in $A - B$ .

If $9 \in C$ , then at least one of 11 or 99 is not in $A - B$ . We map 9 to this element.
If $8 \in C$ , then at least one of 12 or 96 is not in $A - B$ . We map 8 to this element.
If $7 \in C$ , then at least one of 13 or 91 is not in $A - B$ . We map 7 to this element.
If $6 \in C$ , then at least one of 14 or 84 is not in $A - B$ . We map 6 to this element.
If $5 \in C$ , then at least one of 15 or 75 is not in $A - B$ . We map 5 to this element.
If $4 \in C$ , then at least one of 16 or 64 is not in $A - B$ . We map 4 to this element.
If $3 \in C$ , then at least one of 17 or 51 is not in $A - B$ . We map 3 to this element.
If $2 \in C$ , then at least one of 18 or 36 is not in $A - B$ . We map 2 to this element.
Clearly, this map gives us a distinct element in $A - B$ .

Hence, we can show that

$|B| = | ( B \cap \overline{A} ) \dot{\cup} ( B \cap A) | = | C | + | ( B \cap A ) | \leq |A - B | + |B \cap A | = |A| = 91.$

Note: The symbol $\dot { \cup }$ indicates a disjoint union, which is why we can break up the count.

First, note that $S = \{10, 11, 12, \ldots, 100\}$ is a solution, since the product of two distinct integers in $S$ must be at least $10 \times 11 = 110 > 100$ . We have $|S| = 91$ . Is this the maximum?

For each $i \in \{1, 2, 3, \ldots, 9\}$ , at least one of the numbers $i, 20-i, i(20-i)$ are not in $S$ , because the third number is the product of the first two; if all of them are in $S$ , then because $i, 20-i \in S$ , we should have $i \times (20-i) \not\in S$ , but $i \times (20-i) = i(20-i) \in S$ , contradiction. Additionally, it can be verified that the sets $\{i, 20-i, i(20-i)\}$ for all $i \in \{1, 2, \ldots, 9\}$ are pairwise disjoint. Thus at least one number from each set is not in $S$ , for a total of at least 9 such numbers. Thus $|S| \le 100-9 = 91$ , proving that $|S| = 91$ is indeed the maximum.

You can include the numbers 10-100 because the lowest possible product is 10x11 = 110 which is not in S since it is outside the range of numbers 10-100.

Once you include smaller numbers than 10, you are creating possible pairs ab such that 10<=ab<=100. If you include 1, you can make 10 from 1x10. If you include 9, you can make 9x10 = 90 which is in S. Consequently all the numbers 2-9 when multiplied by 10 are in the range 10-90 and therefore these products are in S. So no number 1-9 can be included. Just 10-100. So the answer is 91