Spring 2016, problem 14

A subset $A$ of the set $\{1,2,\dots,10000\}$ has the property that if $a,b$ are distinct elements of $A$, then $ab\not\in A$. What is the maximal number of elements in $A$?

2 years ago

The answer can be the set of all primes from 1 to 10000 including 1 and 2.

A = {set of all primes belonging to {1,2,...,10000} ; including 1 and 2}

2 years ago

Proof:

For brevity give the number 10000 a name: $T := 10000$. Note, that $\sqrt{T}$ is a natural number. Let $M \subset \mathbb{N}$. We say M is consistent, if for all distinct $a, b \in M$ the number $ab$ is not in $M$.

Now define the set $A$ by:

$A := \{\sqrt{T}, \sqrt{T} +1, ..., T\}$.

Then $A$ is quite obviously consistent and $A$ has 9901 elemements. We now prove, that any consistent set $B \subset \{1, 2, ..., T\}$ has at most as many members as $A$. For this we may safely assume, that 1 is not an element of $B$. Otherwise, $B$ could have no further elements, anyway.

Now pick an $x \in B \setminus A$. So $1 \lt x \lt \sqrt{T}$. Write $x = \sqrt{T} - a$, with $a \in \{1, 2, ..., \sqrt{T} - 2\}$. Then since $(\sqrt{T} - a)(\sqrt{T} + a) = T - a^2$, one of the numbers $\sqrt{T} + a$ and $T - a^2$ is not in $B$. But here's the crucial part: If you pick another number $(\sqrt {T}-b )\in B \setminus A$, then the set $\{\sqrt{T} + a, T - a^2\}$ has no members in common with the set $\{\sqrt{T} + b, T - b^2\}$. This is, because $\sqrt{T} + a = T - b^2$ has no solutions with $a$ and $b$ in $\{ 1, ..., \sqrt{T} - 2\}$ (the other non-equalities are trivial to check). So every $x \in B$, that is not also an element of $A$, generates at least one element, that is in $A$, but not in $B$, where the numbers generated this way are all distinct [Put sloppily, whenever you try to add $k$ elements to $A$ you have to lose at least $k$, when trying to stay consistent. Thus you never end up with more elements, than you started with.]. So $B$ has at most as many elements as $A$.

To make the reasoning in the last paragraph clearer, we rewrite it in symbolic language: We have proved, that $\left \vert B \setminus A \right \vert \leq \left \vert A \setminus B \right \vert$ and we use the formula $\left \vert A \right \vert - \left \vert B \right \vert = \left \vert A \setminus B \right \vert - \left \vert B \setminus A \right \vert$ to show that $\left \vert B \right \vert \leq \left \vert A \right \vert$.

2 years ago

Ya This can be done very simply actually i feel. All we need to do is look for the products that exceed 10000.Simple calculation'll verify that 100 . 100 =10000. So max elements can be found out by writing down all the elements from 100 onwards as in {100,101,....10000}. That accounts for 10000 - 99 = 9901 elements as our required answer. Thank you. :)

It's not that simple. Your calculation shows, that the numbers from 100 onward are the maximum set of consecutive numbers that satisfies the conditions. But nobody said, they have to be consecutive. A priori the maximum set could be something more complicated, like the numbers with an odd number of prime factors or something (it is not immediately obvious that this set is not even larger).

Nelix 2 years ago
2 years ago

Will it just be all primes from 1 to 10000, as they cannot be factored into other numbers in the subset? 1229, I believe.

This is what I thought at first, too. But the set of numbers in 1..10000 with an odd number of prime factors also works (counting repetitions in the factorization, too. That is, write out the factorization with no exponents, like prime x prime x prime ... and count the primes). And this set is larger than the set of primes.

Nelix 2 years ago