HMMT 十一月 2016 · THM 赛 · 第 10 题
HMMT November 2016 — THM Round — Problem 10
题目详情
- We have 10 points on a line A , A · · · A in that order. Initially there are n chips on point A . Now 1 2 10 1 we are allowed to perform two types of moves. Take two chips on A , remove them and place one i chip on A , or take two chips on A , remove them, and place a chip on A and A . Find the i +1 i +1 i +2 i minimum possible value of n such that it is possible to get a chip on A through a sequence of moves. 10
解析
- We have 10 points on a line A , A · · · A in that order. Initially there are n chips on point A . Now 1 2 10 1 we are allowed to perform two types of moves. Take two chips on A , remove them and place one i chip on A , or take two chips on A , remove them, and place a chip on A and A . Find the i +1 i +1 i +2 i minimum possible value of n such that it is possible to get a chip on A through a sequence of moves. 10 Proposed by: Allen Liu Answer: 46 We claim that n = 46 is the minimum possible value of n . As having extra chips cannot hurt, it is always better to perform the second operation than the first operation, except on point A . Assign the 1 value of a chip on point A to be i . Then the total value of the chips initially is n . Furthermore, both i types of operations keep the total values of the chips the same, as 2 · 1 = 2 and i + ( i + 2) = 2 · ( i + 1). When n = 46, we claim that any sequence of these moves will eventually lead to a chip reaching A . 10 If, for the sake of contradiction, that there was a way to get stuck with no chip having reached A , 10 then there could only be chips on A through A , and furthermore at most one chip on each. The total 1 9 value of these chips is at most 45, which is less than the original value of chips 46. However, if n ≤ 45, we claim that it is impossible to get one chip to A . To get a chip to A , 10 10 an operation must have been used on each of A through A at least once. Consider the last time 1 9 the operation was used on A for 2 ≤ k ≤ 9. After this operation, there must be a chip on A . k k − 1 Additionally, since no chip is ever moved past A again, there is no point to perform any operations k on any chips left of A , which means that a chip will remain on A until the end. Therefore, if there k k − 1 is a way to get a chip to A , there must also be a way to get a chip to A and also A through A , 10 10 1 8 which means that the original value of the chips must have been already 1 + 2 + · · · + 8 + 10 = 46.