Kvant Math Problem 420

The allowed operations on a fraction $\frac{a}{b}$ replace the integer pair $(a,b)$ by one of $(a-b,b)$, $(a+b,b)$, or $(b,a)$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m11s
Source on kvant.digital

Problem

  1. From the fraction $\dfrac ab$ it is allowed to obtain any of the three fractions $\dfrac{a-b}{b}$, $\dfrac{a+b}{b}$, $\dfrac ba$. Is it possible, using such transformations, to obtain the fraction $\dfrac{67}{91}$ from the fraction $\dfrac 12$?
  2. From a pair of fractions $\left(\dfrac ab, \dfrac cd\right)$ it is allowed to obtain any of the three pairs $\left(\dfrac{a+b}{b}, \dfrac{c+d}{d}\right)$, $\left(\dfrac{a-b}{b}, \dfrac{c-d}{d}\right)$, $\left(\dfrac ba, \dfrac dc\right)$. Is it possible to obtain from the pair of fractions $\left(\dfrac 12, \dfrac 57\right)$ the following pairs: $\left(\dfrac 13, \dfrac 29\right)$; $\left(\dfrac 14, \dfrac 38\right)$; $\left(\dfrac 45, \dfrac 78\right)$; $\left(\dfrac 5{19}, \dfrac{13}{50}\right)$; $\left(\dfrac{39}{50}, \dfrac{60}{77}\right)$? (Here we regard the fraction $\dfrac ab$ simply as a pair of coprime integers: fractions with negative numbers or zero in the numerator or denominator are allowed.)
  3. Try to determine which fractions (respectively, pairs of fractions) can in general be obtained from those given in problems a) and b).

G. A. Gurevich, B. Makarevich

Exploration

The allowed operations on a fraction $\frac{a}{b}$ replace the integer pair $(a,b)$ by one of $(a-b,b)$, $(a+b,b)$, or $(b,a)$. These are elementary integer column operations: adding or subtracting the second component to the first, and swapping coordinates. Such moves preserve $\gcd(a,b)$, since each operation is invertible in integers and does not introduce new common divisors.

Starting from $(1,2)$, the pair is primitive. Any target $(a,b)$ with $\gcd(a,b)=1$ is therefore a candidate. The fraction $\frac{67}{91}$ corresponds to $(67,91)$, and $\gcd(67,91)=1$, so it is consistent with the invariant.

The second part applies the same operation simultaneously to two pairs. This suggests a linear action of the same integer $2\times 2$ matrix on both column vectors. Hence a global invariant such as the determinant of the pair of vectors is expected to be preserved up to sign.

For the initial pair $(1,2)$ and $(5,7)$, the determinant is $1\cdot 7 - 2\cdot 5 = -3$. Any reachable pair must have determinant $\pm 3$. This immediately filters the list.

The key structure is that the allowed operations generate $\mathrm{GL}_2(\mathbb{Z})$, so reachability reduces to orbit questions under unimodular transformations, controlled by determinant invariance.

Problem Understanding

The problem consists of three parts. The first asks whether a single fraction can be transformed into another using elementary integer operations and inversion. This is a Type A classification problem for reachable fractions.

The second asks the same for pairs under synchronized operations, which introduces a coupled invariant between the two components.

The third asks for a general characterization of all reachable objects in both settings.

The central difficulty is identifying the correct invariant structure: for single fractions it is primitivity, while for pairs it is the determinant of the associated integer matrix.

For the first part, the answer is that $\frac{67}{91}$ is reachable from $\frac{1}{2}$.

Proof Architecture

Every allowed operation on a single pair $(a,b)$ corresponds to multiplication by one of the matrices $\begin{pmatrix}1&1\0&1\end{pmatrix}$, $\begin{pmatrix}1&-1\0&1\end{pmatrix}$, or $\begin{pmatrix}0&1\1&0\end{pmatrix}$. These matrices generate $\mathrm{GL}_2(\mathbb{Z})$.

The first lemma is that these operations preserve $\gcd(a,b)$ and hence preserve primitivity. The second lemma is that they generate all unimodular transformations, so every primitive vector lies in the orbit of every other primitive vector.

For the second part, the same matrix acts simultaneously on two vectors. The key lemma is that the determinant of the pair is invariant up to sign under unimodular transformations. The classification reduces to equality of absolute determinant.

The most delicate step is showing that determinant equality is also sufficient, requiring the fact that any two bases of $\mathbb{Z}^2$ with the same orientation up to sign are related by a unique unimodular transformation.

Solution

Part 1

The operations on a fraction correspond to transformations of integer pairs $(a,b)$ by

$$(a,b)\mapsto (a+b,b), \quad (a,b)\mapsto (a-b,b), \quad (a,b)\mapsto (b,a).$$

Each of these operations is invertible over the integers, so they preserve $\gcd(a,b)$.

Since $\gcd(1,2)=1$, every reachable pair $(a,b)$ must satisfy $\gcd(a,b)=1$. The target pair $(67,91)$ satisfies $\gcd(67,91)=1$ since $91=7\cdot 13$ and $67$ is prime and not divisible by $7$ or $13$.

The allowed operations generate the group $\mathrm{GL}_2(\mathbb{Z})$ because the matrices

$$\begin{pmatrix}1&1\0&1\end{pmatrix}, \quad \begin{pmatrix}1&-1\0&1\end{pmatrix}, \quad \begin{pmatrix}0&1\1&0\end{pmatrix}$$

generate all unimodular integer matrices. This group acts transitively on primitive integer vectors.

Since both $(1,2)$ and $(67,91)$ are primitive, there exists $M\in \mathrm{GL}_2(\mathbb{Z})$ such that $M(1,2)=(67,91)$. Therefore the fraction $\frac{67}{91}$ is obtainable.

$$\boxed{\text{Yes, it is possible.}}$$

Part 2

Write fractions as integer vectors. The initial pair corresponds to

$$v_1=(1,2), \quad v_2=(5,7).$$

Each allowed operation applies the same unimodular matrix $M\in \mathrm{GL}_2(\mathbb{Z})$ to both vectors, producing $(Mv_1,Mv_2)$.

Hence every reachable pair is obtained from the initial pair by a common unimodular transformation. The determinant transforms as

$$\det(Mv_1,Mv_2)=\det(M)\det(v_1,v_2).$$

Since $\det(M)=\pm 1$, the quantity $|\det(v_1,v_2)|$ is invariant.

For the initial pair,

$$\det(v_1,v_2)=1\cdot 7-2\cdot 5=7-10=-3,$$

so the invariant is $3$.

A target pair is reachable only if its determinant equals $\pm 3$.

Now evaluate each case.

For $\left(\frac{1}{3},\frac{2}{9}\right)$, the vectors are $(1,3)$ and $(2,9)$, and

$$\det = 1\cdot 9 - 3\cdot 2 = 9-6=3.$$

This matches, so it is reachable.

For $\left(\frac{1}{4},\frac{3}{8}\right)$, the vectors are $(1,4)$ and $(3,8)$, and

$$\det = 1\cdot 8 - 4\cdot 3 = 8-12=-4,$$

which does not equal $\pm 3$, so it is not reachable.

For $\left(\frac{4}{5},\frac{7}{8}\right)$, the vectors are $(4,5)$ and $(7,8)$, and

$$\det = 4\cdot 8 - 5\cdot 7 = 32-35=-3,$$

so it is reachable.

For $\left(\frac{5}{19},\frac{13}{50}\right)$, the vectors are $(5,19)$ and $(13,50)$, and

$$\det = 5\cdot 50 - 19\cdot 13 = 250-247=3,$$

so it is reachable.

For $\left(\frac{39}{50},\frac{60}{77}\right)$, the vectors are $(39,50)$ and $(60,77)$, and

$$\det = 39\cdot 77 - 50\cdot 60 = 3003-3000=3,$$

so it is reachable.

Thus the answers are:

$$\boxed{\text{yes, no, yes, yes, yes}}.$$

Part 3

For a single fraction, the allowed transformations generate all unimodular integer transformations on vectors in $\mathbb{Z}^2$. The invariant is $\gcd(a,b)$, so starting from $(1,2)$, every reachable fraction corresponds exactly to a primitive integer pair $(a,b)$ with $\gcd(a,b)=1$.

For a pair of fractions, the transformations apply the same unimodular matrix to both vectors. Therefore the pair evolves by

$$(v_1,v_2)\mapsto (Mv_1,Mv_2), \quad M\in \mathrm{GL}_2(\mathbb{Z}).$$

The determinant satisfies

$$\det(Mv_1,Mv_2)=\det(M)\det(v_1,v_2),$$

so the absolute value $|\det(v_1,v_2)|$ is invariant.

Conversely, any two ordered bases of $\mathbb{Z}^2$ with the same determinant up to sign are related by a unimodular transformation. Hence a pair is reachable from $( (1,2),(5,7) )$ if and only if the determinant of its representing integer vectors equals $\pm 3$.

Verification of Key Steps

The first delicate point is the claim that the single-fraction operations generate all unimodular transformations. Each operation corresponds to an elementary matrix in $\mathrm{GL}_2(\mathbb{Z})$, and these matrices generate the full group because any unimodular matrix reduces to the identity via the Euclidean algorithm implemented by repeated row operations $(a,b)\mapsto(a\pm b,b)$ and swaps.

The second delicate point is determinant invariance in the pair case. Since both vectors are multiplied by the same matrix $M$, multilinearity of the determinant gives $\det(Mv_1,Mv_2)=\det(M)\det(v_1,v_2)$, and $\det(M)=\pm 1$ for all allowed transformations, ensuring invariance up to sign.

The third point is sufficiency: if two pairs of vectors have equal determinant magnitude, each forms a basis of $\mathbb{Z}^2$ with the same covolume, so the linear map sending one basis to the other has integer matrix and determinant $\pm 1$, placing it in $\mathrm{GL}_2(\mathbb{Z})$.

Alternative Approaches

A different approach to part one uses the Euclidean algorithm directly, reversing it to construct a sequence of additions and swaps that builds $(67,91)$ from $(1,2)$.

For part two, one may encode each pair as a $2\times 2$ integer matrix and observe that the transformations correspond to left multiplication by $\mathrm{GL}_2(\mathbb{Z})$, reducing the problem to classification of matrices up to left multiplication, where determinant is the only invariant of full-rank orbits.