Maths Olympiad Prep

Library / /4 of 6

Algebra Difficulty 7.5 National olympiad, round 2 Find the answer

Two different integers uu and vv are written on a board. We perform a sequence of steps. At each step we do one of the following two operations:

(i) If aa and bb are different integers on the board, then we can write a+ba + b on the board, if it is not
already there.
(ii) If aa, bb and cc are three different integers on the board, and if an integer xx satisfies ax2+bx+c=0ax^2 +bx+c = 0,
then we can write xx on the board, if it is not already there.

Determine all pairs of starting numbers (u,v)(u, v) from which any integer can eventually be written on the board after a finite sequence of steps.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve this problem, we need to explore the operations provided and determine the conditions under which any integer can eventually be written on the board starting from a pair (u,v)(u,v).

1. Initial Setup:
We begin with two distinct integers u u and v v on the board. At each operation, we can:
- Add two distinct integers a a and b b to form a+b a + b , or
- Use three distinct integers a a , b b , and c c to find roots x x of the quadratic equation ax2+bx+c=0 ax^2 + bx + c = 0 .

2. Operation (i) Insight:
- Using the first operation, we can generate any linear combination of integers on the board. Thus, if we can reach any integer through linear combinations, then having all integers equals the ability to construct them through the sum operation.

3. Operation (ii) Insight:
- The second operation broadens our potential to generate integers on the board beyond linear combinations. Specifically, solving quadratic equations brings the prospects of writing quadratic roots, which can include integers beyond immediate integer sums.

4. Key Restrictions Analysis:
- Consider the integers on the board. If all integers can be obtained, we must have a way to generate both positive and negative integers. Thus, initial integers must allow us to cross zero in some fashion.

5. Finding Robust Initial Conditions:
- If u u and v v are non-zero and at least one of them is positive, then using additions and positive/negative combinations, we can eventually reach any integer, positive or negative.
- However, starting with opposite signs and both non-zero, say (1,1)(-1, 1) or (1,1)(1, -1), notice that:
- The only sums directly achievable from these are 0 or integers closer to each other symmetrically reducing chances of crossing zero for positive convergence or broader exploration.

6. Deriving the Condition:
Therefore, the pairs (u,v)(u, v) that allow us to eventually write any integer on the board must satisfy:
- Both numbers are non-zero u0 u \neq 0 , v0 v \neq 0 ,
- At least one of them is positive i.e. max(u,v)>0\max(u, v) > 0,
- Exclude the pairs (1,1)(-1, 1) and (1,1)(1, -1) since they restrict reaching all integers.

Thus, the required pairs (u,v)(u, v) are:

All pairs (u,v) of distinct integers for which u0,v0,max(u,v)>0, and (u,v){(1,1),(1,1)}. \boxed{\text{All pairs } (u, v) \text{ of distinct integers for which } u \neq 0, v \neq 0, \max(u, v) > 0, \text{ and } (u, v) \notin \{(-1, 1), (1, -1)\}.}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.