HMMT 二月 2017 · 冲刺赛 · 第 9 题

HMMT February 2017 — Guts Round — Problem 9

[ 7 ] Jeffrey writes the numbers 1 and 100000000 = 10 on the blackboard. Every minute, if x, y are on the board, Jeffrey replaces them with ( ) − 1 x + y 1 1 and 2 + . 2 x y After 2017 minutes the two numbers are a and b . Find min( a, b ) to the nearest integer.

解析

[ 7 ] Jeffrey writes the numbers 1 and 100000000 = 10 on the blackboard. Every minute, if x, y are on the board, Jeffrey replaces them with ( ) − 1 x + y 1 1 and 2 + . 2 x y After 2017 minutes the two numbers are a and b . Find min( a, b ) to the nearest integer. Proposed by: Yang Liu Answer: 10000 Note that the product of the integers on the board is a constant. Indeed, we have that ( ) − 1 x + y 1 1 · 2 + = xy. 2 x y √ 4 8 Therefore, we expect that the answer to the problem is approximately 1 · 10 = 10 . To be more rigorous, we have to show that the process indeed converges quickly enough. To show this, we bound the difference between the integers on the board at time i . Say that at time i , the integers on the board are a < b . Note that i i ( ) − 1 2 a + b 1 1 ( a − b ) i i i i d = b − a = − 2 + = i +1 i +1 i +1 2 a b 2( a + b ) i i i i b − a d i i i < = . 2 2 d i The inequality at the end follows from that obvious fact that b − a < b + a . Therefore, d ≤ , so i i i i i +1 2 8 10 d < , which is extremely small. So the difference is essentially 0 at time 2017, which completes 2017 2017 2 the argument.