Library / /38 of 48

, 2008

Number theory Difficulty 6.5 National Olympiad Prove it Hong Kong

Let $x_1$ and $y_1$ be positive integers satisfying $x_1 + y_1 = 2^r$ , where $r$ is a positive integer. If $x_1 < y_1$ , let $x_2 = 2x_1$ and $y_2 = 2^r - x_2$ . On the other hand, if $x_1 > y_1$ , then we let $y_2 = 2y_1$ and $x_2 = 2^r - y_2$ . Apply the same procedure to $(x_2, y_2)$ , and so on. Show that the procedure will end in finitely many steps, i.e. there exists a $k$ such that $x_k = y_k$ . (For example, let $(x_1, y_1) = (7, 57)$ , with $x_1 + y_1 = 2^6$ . Then $(x_2, y_2) = (14, 50)$ , $(x_3, y_3) = (28, 36)$ , $(x_4, y_4) = (56, 8)$ , $(x_5, y_5) = (48, 16)$ , and finally $(x_6, y_6) = (32, 32)$ .)

Solution

Note that for any positive integers $x$ and $y$ satisfying $x + y = 2^r$ , we have
$v_2(x) = v_2(2^r - y) = v_2(y),$
where $v_2(n)$ is the largest $m$ such that $2^m \mid n$ . Therefore, WLOG we may assume $x_k < y_k$ in some step. Since
$v_2(x_{k+1}) = v_2(2x_k) = v_2(x_k) + 1,$
the sequence $\{v_2(x_k)\}_{k \ge 1}$ is strictly increasing. But then the sequence is bounded above by $r-1$ since $x_k < 2^r$ . Therefore, it must be a finite sequence, which means the procedure will end in finitely many steps.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.