A pair of positive integers $m, n$ is called guerrera, if there exists positive integers $a, b, c, d$ such that $m=ab$, $n=cd$ and $a+b=c+d$. For example the pair $8, 9$ is guerrera cause $8= 4 \cdot 2$, $9= 3 \cdot 3$ and $4+2=3+3$. We paint the positive integers if the following order: We start painting the numbers $3$ and $5$. If a positive integer $x$ is not painted and a positive $y$ is painted such that the pair $x, y$ is guerrera, we paint $x$. Find all positive integers $x$ that can be painted.
Problem
Source: Mexican Mathematical Olympiad 2016-Problem 2
Tags:
08.11.2016 02:32
Cute problem! Define the following triangle so that the $i^{\text{th}}$ row has $\lceil\tfrac{i}{2}\rceil$ entries, and the $j^{\text{th}}$ column consists of the multiples of $j$ starting with $j^2$. The central idea is to show that every row starting with the sixth contains at least one element that occurs in a previous row. But this is true; we consider the first entry of a row if it is composite, the second otherwise. The rest is just strong induction on the rows. The final answer should be $\boxed{\mathbb Z^{+}\setminus \{1,2\}}$
08.11.2016 03:12
Can you please show what $\boxed{\mathbb Z^{+}\setminus \{1,2\}}$ means for the first several terms? Thanks
08.11.2016 03:15
All positive integers but $1$ and $2$.
08.11.2016 05:09
I suppose I should be more explicit about the solution. Again we will construct the triangle. An image of the first sixteen rows is attached below. The motivation behind the construction is that two entries in the same row must be "guererra." Specifically, the $i^{\text{th}}$ row is the set of $n\in\mathbb Z^{+}$ such that there exist $a,b\in\mathbb Z^{+}$ satisfying $a+b=i+1$. Note that one integer can show up in many places on the triangle (in fact this is the crux of the solution). What our operation does is paint every unpainted row containing a integer that is (somehwere else) painted. It is easy to check that the third, fourth, and fifth rows are painted after a few iterations of the operation. Now, consider the $i^{\text{th}}$ row where $i\geq 6$. If the first entry, which is $i$, is composite, then there is an "earlier" row containing $i$. This is because if we write $i=ab$ with $a,b>1$ then $i=1+(i-1)>a+b$. Otherwise if $i$ is prime then $i-1$ is not prime, and then the second entry, $2(i-1)$ can be factored as $ab$ with $a,b>2$ whenever $i\geq 7$, and again we can get $i=2+(i-2)>a+b$. Now suppose all the rows less than $i$ are painted (excluding the first and the second). Then some element of row $i$ must be painted, and hence row $i$ will also get painted. In this manner we obtain the answer $\boxed{\mathbb Z^{+}\setminus \{1,2\}}$ Edit: I know that my typing is not so good; please ask questions if anything is unclear.
Attachments:

04.04.2019 12:04
The main idea is to note $2ab=(2a)b=(2b)a$. Thus $2a+b-1=(2a+b-1)1$ is guerrera with $2ab$ which is also guerrera with $2b+a-1$. Thus for positive integers $a,b$, $2a+b-1$ is coloured iff $2b+a-1$ is. Substitute $b=a+1$; then $2a+(a+1)-1=3a$ is coloured iff $2(a+1)+a-1=3a+1$ is too. Subs $b=a+2$; $2a+(a+2)-1=3a+3$ iff $2a+(a+2)-1=3a+1$. Given that $3$ is coloured, we get that all $3a,3a+1$ ($a$ positive) is coloured. Substitute $b=a+3$; then $2a+(a+3)-1=3a+2$ is coloured iff $2(a+3)+a-1=3a+5$. Then as $5$ is coloured, all $3a+2$ ($a$ positive) is coloured. 2,1 are uncoloured as there are not guerrera with any other number. So all $\mathbb Z^{+} \setminus \{1,2\}$ is coloured.