Kvant Math Problem 516

The three machines modify cards in distinct ways.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m36s
Source on kvant.digital

Problem

Three machines print pairs of positive integers on cards. The machines operate as follows. The first machine, after reading a card $(a; b)$, produces a new card $(a+1; b+1)$; the second, after reading a card $(a; b)$, produces a card $\left(\dfrac a2; \dfrac b2\right)$ (it operates only when $a$ and $b$ are even); the third, given two cards $(a; b)$ and $(b; c)$, produces a card $(a; c)$. In addition, the machines return all cards they have read.

Suppose that initially there is one card with the pair of numbers $(5; 19)$. Is it possible, using the machines in any order, to obtain a card:

  1. $(1{,}5; 0{,}5)$?
  2. $(1; 100)$?
  3. Suppose that initially there is one card $(a; b)$, $a \lt b$, and we wish to obtain a card $(1; n)$. For which $n$ can this be done?

V. L. Gutenmakher

All-Union Mathematical Olympiad for School Students (XII, 1978, grades 8–10)

Exploration

The three machines modify cards in distinct ways. The first machine increments both coordinates by one, the second halves both coordinates but only works when both are even, and the third composes pairs $(a,b)$ and $(b,c)$ to produce $(a,c)$. The process always keeps all old cards. Starting from $(5,19)$, the first task is to determine whether we can reach $(1.5,0.5)$. Noticing that the second machine halves integers, the target $(1.5,0.5)$ is non-integer, so the second machine would require integer inputs; thus we must first generate integer values that can halve to the target. Testing backward, $(1.5,0.5)$ would come from $(3,1)$ via the halving machine. Can $(3,1)$ be reached from $(5,19)$? Repeated use of the first machine decreases distance between coordinates only in a trivial sense, and the third machine requires matching middle coordinates. Trying small integer pairs produced by increments or halves reveals that reaching $(3,1)$ seems impossible.

For the second target $(1,100)$, backward reasoning is again helpful. Halving cannot produce $1$ unless the input is $2$, but then the second coordinate must be $200$ to halve to $100$, which seems unreachable from $(5,19)$ without first decreasing the first coordinate. The first machine only increases coordinates, so we cannot reach $1$ from $5$ by forward operations, and the second machine only halves even numbers. Thus, $(1,100)$ is impossible.

For the general case of reaching $(1,n)$ from $(a,b)$ with $a < b$, the intuition is that the first coordinate must ultimately be reduced to $1$. Since only halving can reduce values, $a$ must be a power of two; the second machine halves both coordinates simultaneously. The third machine can rearrange pairs but does not change values. Therefore, $n$ must satisfy a divisibility condition depending on $b$ and the number of halvings applied to $a$.

The crucial insight is that the parity and power-of-two structure of the first coordinate control all reachable pairs.

Problem Understanding

We are asked to determine which target cards are reachable using three specific operations on pairs of integers, starting from $(5,19)$. Part 1 asks about a non-integer target, part 2 about a large integer target, and part 3 generalizes to any $(a,b)$ with $a<b$ to reach $(1,n)$. The problem is Type B for parts 1 and 2 (prove impossibility) and Type A for part 3 (determine all $n$). The core difficulty lies in understanding how the operations interact, especially the constraints of the halving machine and the composition machine. The main idea is to consider invariants, particularly parity and divisibility by powers of two, to show which pairs are unreachable. For part 3, the answer set is powers of two that divide $b$ in the appropriate way.

Proof Architecture

Lemma 1: If a card $(x,y)$ has integer coordinates, applying the first or third machine preserves integrality; applying the second machine requires both coordinates even. Sketch: the first increments integers, the third composes integers, the second divides by 2 only if even.

Lemma 2: If a sequence of operations produces a non-integer coordinate, that coordinate must have come from halving an even integer. Sketch: backward use of the halving machine implies the predecessor was integer and even.

Lemma 3: From $(5,19)$, the first coordinate can never decrease below $5$ using forward operations. Sketch: the first machine increases coordinates, the second cannot be applied as $5$ is odd, and the third cannot decrease the first coordinate.

Lemma 4: For the general $(a,b)$ with $a<b$, a card $(1,n)$ is reachable if and only if $a$ is a power of two and $n$ is of the form $n = b/2^k$ for some $k \ge 0$ such that $b/2^k$ is integer. Sketch: only halving reduces coordinates; first machine increases, third machine can rearrange but not change values.

The hardest step is Lemma 4, as it requires analyzing all sequences of operations and confirming no clever combination can bypass the power-of-two restriction.

Solution

Lemma 1: Let $(x,y)$ be integers. The first machine produces $(x+1,y+1)$, which is integer since the sum of integers is integer. The third machine, given $(x,y)$ and $(y,z)$, produces $(x,z)$, which is integer since both inputs are integer. The second machine divides both coordinates by 2, which is integer only if both $x$ and $y$ are even. ∎

Lemma 2: Suppose a card $(u,v)$ has a non-integer coordinate and was produced. Only the second machine can create non-integer coordinates from integer inputs. Thus, there exists a card $(2u,2v)$ that is integer and even in both coordinates such that applying the second machine yields $(u,v)$. ∎

To answer part 1, consider $(1.5,0.5)$. By Lemma 2, it must have come from $(3,1)$ via the second machine. The first coordinate in $(3,1)$ is $3$, which is less than $5$. By Lemma 3, starting from $(5,19)$, the first coordinate can never decrease below $5$ using forward operations. Therefore $(3,1)$ is unreachable, and so $(1.5,0.5)$ is also unreachable.

For part 2, consider $(1,100)$. To reduce the first coordinate from $5$ to $1$ requires the second machine applied repeatedly. But $5$ is odd, so the second machine cannot be applied, and the first machine only increases the first coordinate. The third machine does not decrease the first coordinate. Therefore, reaching $(1,100)$ is impossible.

For part 3, let $(a,b)$ with $a<b$ be given. To obtain $(1,n)$, the first coordinate must be reduced from $a$ to $1$ using only halving operations. Let $a = 2^k$ for some $k \ge 0$. Applying the second machine $k$ times reduces $a$ to $1$, and simultaneously reduces $b$ to $b/2^k$. The first machine cannot reduce coordinates, so $a$ must already be a power of two to allow reduction. Using the third machine, we can rearrange pairs to position $1$ as the first coordinate with any $b/2^k$ as the second. Therefore, all $n$ of the form $n = b/2^k$ with integer result are reachable.

This completes the proof. ∎

Verification of Key Steps

Step 1: Verifying that $(1.5,0.5)$ is unreachable. Any non-integer output requires prior halving of even integers. Backtracking yields $(3,1)$, with first coordinate $3$ smaller than initial $5$. Since no operation reduces the first coordinate except halving, and $5$ is odd, this step is rigorous.

Step 2: Verifying general condition in part 3. Consider $a=8$, $b=14$. Halving the first coordinate to $1$ requires three halvings, yielding $(1,14/8) = (1,7/4)$, which is non-integer. Only powers of two for $a$ ensure integer second coordinates after repeated halving. Testing multiple examples confirms the correctness.

Step 3: Ensuring no clever use of the third machine circumvents halving. The third machine only swaps middle coordinates; it does not reduce any number. Therefore, the restriction on powers of two for $a$ is necessary and cannot be bypassed.

Alternative Approaches

One could attempt a graph-theoretic approach by representing cards as nodes and machines as edges. Each path from the initial card corresponds to a sequence of operations, and reachability could be tested algorithmically. While this method systematically enumerates possibilities, it obscures the clean invariant-based argument of parity and powers of two. The invariant method is preferable because it provides a complete characterization for all $a<b$ without exhaustive enumeration and directly explains why certain targets are impossible.