HMMT 十一月 2016 · THM 赛 · 第 10 题

英文解析

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 oneichip on A , or take two chips on A , remove them, and place a chip on A and A . Find thei +1 i +1 i +2 iminimum possible value of n such that it is possible to get a chip on A through a sequence of moves.
    Proposed by: Allen Liu 10
    Answer: 46
    We claim that n = 46 is the minimum possible value of n . As having extra chips cannot hurt, it isalways better to perform the second operation than the first operation, except on point A . Assign the value of a chip on point A to be i . Then the total value of the chips initially is n . Furthermore, both 1
    types of operations keep the total values of the chips the same, as 2 · 1 = 2 and i + ( i + 2) = 2 · ( i + 1).i
    When n = 46, we claim that any sequence of these moves will eventually lead to a chip reaching A .
    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 10
    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 operationskon any chips left of A , which means that a chip will remain on A until the end. Therefore, if therek 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.