Which number can I erase?

Question

All positive integers greater than $2$ are written on a board. First we erase number $3$ and $5$.

With 4 positive integers $a,b,c,d$ satisfying $a+b=c+d$, if $ab$ is erased, then $cd$ can be erased, otherwise $cd$ cannot be erased.

For example, $3=3 \times 1$, $3+1=4=2+2$ , then $2 \times 2 = 4$ is erased.

a. What are the conditions of a number that can be erased ?

b. If not only $3$ and $5$, but every prime number is erased at the beginning, can all other numbers be erased as well? If not, what are the conditions of a number to be erased ?

(Sorry for my last question, English is my second language)

Answer 1

A prime $p>5$ can be erased if $m=2(p-1)$ has been erased, as $2+(p-1)=p+1$. Note that $$m=2\times(p-1)=4\times\frac{p-1}{2},$$ where $p-1$ is even because $p>5$ is prime. This factorization of $m$ shows that it can be erased if $\frac{p+5}{2}$ has been erased, because $$\frac{p-1}{2}+4=\frac{p+5}{2}+1,$$ where clearly $\frac{p+5}{2}<p$ becase $p>5$.

A composite number $n=uv$ with $u,v>1$ can be erased if $m=u+v-1$ has been erased, as $$1+(u+v-1)=u+v.$$ Of course $m<n$ because $u,v>1$.

In particular, an integer $n>5$ can be erased if all integers less than $n$ have been erased, so you can use induction.

Answer 2

Somewhat a long comment (not a complete answer).

The first thing that I would suggest is that you should work through some examples and see what happens. I'll help with some of the initial steps.

To think about what you're erasing, let $n$ be a number that has been erased. Then, for each pair of factors $ab$ so that $ab=n$, compute $a+b=m$. Next, you find all other ways to write $m$ as a sum $m=c+d$ and then delete each $cd$ found in this way. Then, you continue until there isn't anything more to delete (or you see the pattern).

In your set-up, you start with $3$ and $5$ deleted.

Deleted: $3$ and $5$.

• Using the deleted $3$, you know that $3$ factors as $3=1\cdot 3$. Therefore, $a+b=1+3=4$. The only sums equal to $4$ are $1+3$ and $2+2$. Taking $c=2$ and $d=2$ gives $cd=4$, so $4$ is deleted. Since we've considered all pairs of factors of $3$, there is nothing more that $3$ can tell us.

Deleted: $3$, $4$, and $5$.

• Using the deleted $4$, you know that $4$ factors as $4=1\cdot 4$ or $2\cdot 2$. In the first case, $1+4=5$, and $5$ can be written as $5=1+4$ or $5=2+3$. The first case leads to $1\cdot 4=4$, which is already deleted, but $2\cdot 3=6$, which can now be deleted. On the other hand, using $2\cdot 2=4$, we have two ways to write $4$ as a sum, $4=1+3$ or $4=2+2$. In either case, the product is $1\cdot 3=3$ or $2\cdot 2=4$, both of which have already been deleted. Therefore, there is nothing more that $4$ can tell us.

Deleted: $3$, $4$, $5$, and $6$.

• Using the deleted $5$, you know that $5$ factors as $1\cdot 5=5$. Therefore, the sum of these two is $1+5=6$. There are three ways to write $6$ as a sum, $1+5=6$, $2+4=6$, and $3+3=6$. The first pair has product $1\cdot 5=5$, which has already been deleted. The second pair has product $2\cdot 4=8$, which can now be deleted. The third pair has product $3\cdot 3=9$, which can also be deleted.

Deleted: $3$, $4$, $5$, $6$, $8$, and $9$.

• Using the deleted $6$, you know that $6$ factors as $1\cdot 6=6$ and $2\cdot 3=6$. Therefore, the corresponding sums are $1+6=7$ or $2+3=5$. There are three sums to get $7$, $1+6=7$, $2+5=7$, and $3+4=7$. There are two sums to get $5$, $1+4=5$ and $2+3=5$. These, combined allow one to delete $6$, $10$, $12$, $4$, and 6$.

Deleted: $3$, $4$, $5$, $6$, $8$, $9$, $10$, and $12$.

Continue this until you find a pattern.