PUMaC 2017 · 数论（A 组） · 第 1 题
PUMaC 2017 — Number Theory (Division A) — Problem 1
题目详情
- Shaq sees the numbers 1 through 2017 written on a chalkboard. He repeatedly chooses three numbers, erases them, and writes one plus their median. (For instance, if he erased − 2 , − 1 , 0 he would replace them with 0.) If M is the maximum possible final value remaining on the board, and if m is the minimum, compute M − m .
解析
- Claim: M = 2017 , m = 3. m ≥ 1 + min { 1 , 2 , . . . , 2017 } = 2. However, for m = 2, then it comes from a triple with median 1, which requires another element less than or equal to 1, which cannot occur. Instead, we can explicitly describe a process to construct m = 3; for the first 1007 iterations, only choose from { 3 , 4 , . . . , 2017 } . Then simply choose the three remaining values: 1, 2 and a value greater than
In order to obtain M > 2017 we would need to get an element in the list equal to 2017 and an element greater than 2017. However, this is impossible, since when there is an element equal to 2017 there cannot be one greater. Instead, we can explicitly describe a process to construct M = 2017; for the first 1007 iterations, only choose from { 1 , 2 , . . . , 2015 } . Then simply choose the three remaining values: a value less than or equal to 2015, 2016 and 2017. M − m = 2014 . Problem written by Zack Stier