Maths Olympiad Prep

Library / /105 of 520

Number theory Difficulty 5.7 AIME, harder Find the answer

From a sequence of integers (a,b,c,d)(a, b, c, d) each of the sequences

(c,d,a,b),(b,a,d,c),(a+nc,b+nd,c,d),(a+nb,b,c+nd,d), (c, d, a, b),(b, a, d, c),(a+n c, b+n d, c, d),(a+n b, b, c+n d, d),

for arbitrary integer nn can be obtained by one step. Is it possible to obtain (3,4,5,7)(3,4,5,7) from (1,2,3,4)(1,2,3,4) through a sequence of such steps?

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

Solutions — 2

Solution 1

Answer: no.

Under all transformations (a,b,c,d)(a,b,c,d)(a, b, c, d) \rightarrow\left(a^{\prime}, b^{\prime}, c^{\prime}, d^{\prime}\right) allowed in the problem we have adbc=adbc|a d-b c|=\left|a^{\prime} d^{\prime}-b^{\prime} c^{\prime}\right|, but 1423=21=3745|1 \cdot 4-2 \cdot 3|=2 \neq 1=|3 \cdot 7-4 \cdot 5|.

Remark. The transformations allowed in the problem are in fact the elementary transformations of the determinant

abcd \left|\begin{array}{ll} a & b \\ c & d \end{array}\right|

and the invariant adbc|a d-b c| is the absolute value of the determinant which is preserved under these transformations.

Solution 2

1. Define the invariant: For a quadruple (p,q,r,s)(p, q, r, s), let NN denote psqr|ps - qr|. We will show that NN is invariant under the given transformations.

2. Check invariance under each transformation:
- For the transformation (a,b,c,d)(c,d,a,b)(a, b, c, d) \to (c, d, a, b):
N=psqr=adbc N = |ps - qr| = |ad - bc|
After transformation, we have:
N=cbda=adbc=N N' = |cb - da| = |ad - bc| = N
- For the transformation (a,b,c,d)(b,a,d,c)(a, b, c, d) \to (b, a, d, c):
N=psqr=adbc N = |ps - qr| = |ad - bc|
After transformation, we have:
N=badc=adbc=N N' = |ba - dc| = |ad - bc| = N
- For the transformation (a,b,c,d)(a+nc,b+nd,c,d)(a, b, c, d) \to (a + nc, b + nd, c, d):
N=psqr=adbc N = |ps - qr| = |ad - bc|
After transformation, we have:
N=(a+nc)d(b+nd)c=ad+ncdbcndc=adbc=N N' = |(a + nc)d - (b + nd)c| = |ad + ncd - bc - ndc| = |ad - bc| = N
- For the transformation (a,b,c,d)(a+nb,b,c+nd,d)(a, b, c, d) \to (a + nb, b, c + nd, d):
N=psqr=adbc N = |ps - qr| = |ad - bc|
After transformation, we have:
N=(a+nb)db(c+nd)=ad+nbdbcbnd=adbc=N N' = |(a + nb)d - b(c + nd)| = |ad + nbd - bc - bnd| = |ad - bc| = N

3. **Calculate NN for the initial and target quadruples**:
- For the initial quadruple (1,2,3,4)(1, 2, 3, 4):
N=1423=46=2 N = |1 \cdot 4 - 2 \cdot 3| = |4 - 6| = 2
- For the target quadruple (3,4,5,7)(3, 4, 5, 7):
N=3745=2120=1 N = |3 \cdot 7 - 4 \cdot 5| = |21 - 20| = 1

4. Compare the invariants: Since NN is invariant under the given transformations, and the initial NN is 2 while the target NN is 1, it is impossible to transform (1,2,3,4)(1, 2, 3, 4) into (3,4,5,7)(3, 4, 5, 7) using the given transformations.

\blacksquare

The final answer is False

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.