Maths Olympiad Prep

Library / /200 of 520

Number theory Difficulty 6.7 National olympiad Find the answer

A pair of positive integers m,nm, n is called [i]guerrera[/i], if there exists positive integers a,b,c,da, b, c, d such that m=abm=ab, n=cdn=cd and a+b=c+da+b=c+d. For example the pair 8,98, 9 is [i]guerrera[/i] cause 8=428= 4 \cdot 2, 9=339= 3 \cdot 3 and 4+2=3+34+2=3+3. We paint the positive integers if the following order:

We start painting the numbers 33 and 55. If a positive integer xx is not painted and a positive yy is painted such that the pair x,yx, y is [i]guerrera[/i], we paint xx.

Find all positive integers xx that can be painted.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine which positive integers can be painted based on the given rules. We start by understanding the concept of a *guerrera* pair and then proceed to analyze the painting process.

1. **Definition of a *guerrera* pair**:
A pair of positive integers (m,n) (m, n) is called *guerrera* if there exist positive integers a,b,c,d a, b, c, d such that:
m=ab,n=cd,anda+b=c+d m = ab, \quad n = cd, \quad \text{and} \quad a + b = c + d
For example, (8,9) (8, 9) is a *guerrera* pair because 8=42 8 = 4 \cdot 2 , 9=33 9 = 3 \cdot 3 , and 4+2=3+3 4 + 2 = 3 + 3 .

2. Initial painted numbers:
We start by painting the numbers 3 3 and 5 5 .

3. Painting process:
If a positive integer x x is not painted and there exists a painted positive integer y y such that (x,y) (x, y) is a *guerrera* pair, then we paint x x .

4. Constructing the triangle:
We construct a triangle where the i i -th row consists of integers n n such that there exist a,bZ+ a, b \in \mathbb{Z}^+ satisfying a+b=i+1 a + b = i + 1 . This means the i i -th row contains all products ab ab where a+b=i+1 a + b = i + 1 .

5. Painting the rows:
- The third row contains 3 3 (since 3=13 3 = 1 \cdot 3 and 1+3=4 1 + 3 = 4 ).
- The fourth row contains 4 4 (since 4=22 4 = 2 \cdot 2 and 2+2=4 2 + 2 = 4 ).
- The fifth row contains 5 5 (since 5=15 5 = 1 \cdot 5 and 1+5=6 1 + 5 = 6 ).

6. **General case for i6 i \geq 6 **:
- If i i is composite, then i=ab i = ab with a,b>1 a, b > 1 . Since a+bi a + b \leq i , there is an earlier row containing i i .
- If i i is prime, then i1 i - 1 is not prime. The second entry in the row, 2(i1) 2(i-1) , can be factored as ab ab with a,b>2 a, b > 2 whenever i7 i \geq 7 . Thus, i=2+(i2)a+b i = 2 + (i - 2) \leq a + b .

7. Inductive argument:
Suppose all rows less than i i are painted (excluding the first and second rows). Then some element of row i i must be painted, and hence row i i will also get painted.

8. Conclusion:
By induction, all positive integers x3 x \geq 3 will eventually be painted. The only integers that cannot be painted are 1 1 and 2 2 .

The final answer is Z+{1,2}\boxed{\mathbb{Z}^+ \setminus \{1, 2\}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.