Spring 2016, problem 14

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}

The answer is 9901.

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$.

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. :)

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

I think the answer is 9901. The set A with 9901 elements is {100, 101, ..., 10000}.

Jao

The answer to this question is 10,000.

Best Essay Writing Service on Reddit (2022)

There are many writing services that claim to be the best but there is only one that Redditors say is the best.

If you’re looking for essay and essay writing service, you should look at the following digital agencies:

• PaperHelp: It has a wide variety of essays and essay writing services to offer. You can upload your paper and get feedback from their experts or you can use their service for help.
• ExtraEssay: They provide quality essays and essay writing services at an affordable price.
• EssayPro: They also provide quality essays and essay writing services at an affordable price.