Find all sets $ A$ of nonnegative integers with the property: if for the nonnegative intergers $m$ and $ n $ we have $m+n\in A$ then $m\cdot n\in A.$
Problem
Source: Moldova TST 2023
Tags: combinatorics
09.04.2023 16:13
$A=\emptyset$ works. Suppose $A$ is not empty. $A=\left \{0\right \}$ works, now assume that $A$ has at least one non zero element. If $a\in A,a\neq 0$ then $1+(a-1)\in A$ so $1\cdot(a-1)=a-1\in A$. As a result, if $A$ is finite then is on the form $A=\left \{0,1,..,n\right \}$, if is not finite then $A=Z_{\geq 0}$ In the finite case, if $n\geq 5$ then $2+n-2\in A$ so $2(n-2)\in A\Rightarrow 2n-4\leq n\Rightarrow n\leq 4$ a contradiction. So $A=\emptyset,\left \{0\right \},\left \{0,1\right \},\left \{0,1,2\right \},\left \{0,1,2,3\right \},\left \{0,1,2,3,4\right \},Z_{\geq 0}$ are the only solutions.
11.04.2023 00:11
$A=\emptyset$, $A=\{0\}$, $A=\{0,1\}$, $A=\{0,1,2\}$, $A=\{0,1,2,3\}$, $A=\{0,1,2,3,4\}$, $A=\mathbb Z_{\ge0}$ work, now assume $A$ is something else. If $n\in A$ then we can conclude $\{0,1,\ldots,n\}\subseteq A$ by inductively applying $(n-1)+1\in A\Rightarrow n-1\in A$. If $A$ is unbounded above, we get $A=\mathbb Z_{\ge0}$ using this, which is impossible, so let $\max A=a$. If $a\le4$ we get one of the aforementioned sets, and if $a=5,6$ we get $2\cdot3=6\in A$ and $3\cdot3=9\in A$ which is a contradiction, so $a\ge7$. Then $\left\lfloor\frac a2\right\rfloor+\left\lceil\frac a2\right\rceil=a\in A$, so: $$A\ni\left\lfloor\frac a2\right\rfloor\left\lceil\frac a2\right\rceil\ge\left(\frac a2-1\right)\left(\frac a2\right)>a$$since $a\ge7$, contradiction.