返回题库

HMMT 十一月 2017 · 团队赛 · 第 10 题

HMMT November 2017 — Team Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 70 ] Yannick has a bicycle lock with a 4-digit passcode whose digits are between 0 and 9 inclusive.
    (Leading zeroes are allowed.) The dials on the lock is currently set at 0000. To unlock the lock, everysecond he picks a contiguous set of dials, and increases or decreases all of them by one, until the dialsare set to the passcode. For example, after the first second the dials could be set to 1100 , 0010 , or
    9999, but not 0909 or 0190. (The digits on each dial are cyclic, so increasing 9 gives 0, and decreasing
    0 gives 9.) Let the complexity of a passcode be the minimum number of seconds he needs to unlockthe lock. What is the maximum possible complexity of a passcode, and how many passcodes have thismaximum complexity? Express the two answers as an ordered pair.
解析

英文解析

  1. [ 70 ] Yannick has a bicycle lock with a 4-digit passcode whose digits are between 0 and 9 inclusive.
    (Leading zeroes are allowed.) The dials on the lock is currently set at 0000. To unlock the lock, everysecond he picks a contiguous set of dials, and increases or decreases all of them by one, until the dialsare set to the passcode. For example, after the first second the dials could be set to 1100 , 0010 , or
    9999, but not 0909 or 0190. (The digits on each dial are cyclic, so increasing 9 gives 0, and decreasing
    0 gives 9.) Let the complexity of a passcode be the minimum number of seconds he needs to unlockthe lock. What is the maximum possible complexity of a passcode, and how many passcodes have thismaximum complexity? Express the two answers as an ordered pair.
    Proposed by: Yuan Yao
    Answer: (12 , 2)
    To simplify the solution, we instead consider the equivalent problem of reducing a passcode to 0000
    using the given move.
    Given a passcode a a a a , define a differential of the passcode to be a quintuple ( d , d , d , d , d )
    1 2 3 4 1 2 3 4 5
    such that d ≡ a − a (mod 10) for i = 1 , 2 , 3 , 4 , 5, where we define a = a = 0.
    i i i − 1 0 5
    Claim 1: For any passcode, there exists a differential that satisfies the following two conditions:
    • d + d + d + d + d = 0;
    1 2 3 4 5
    • The range (difference between the maximum and minimum) of these five numbers is at most 10.
    Proof: We first see that the differential defined by d = a − a satisfy the first condition since thei i i − 1
    sum of the five numbers is a − a = 0. Suppose that a differential satisfying the first condition has a
    5 0
    range greater than 10, then we take one of the largest number d and one of the smallest number dm n
    (where d − d > 10), and replace the former by d − 10 and the latter by d + 10. This will eitherm n m nreduce the range or reduce the number of maximal and minimal numbers, so the process will terminateafter finitely many iterations. Thus we can find a differential that satisfies both conditions.
    (Note: we call such a differential a standard differential from now on, although it is important toremember that there may be more than one standard differential for one passcode. As a corollary, allof the numbers in a standard differential must be in the range [ − 9 , 9], as a number greater than 9 will be more than 10 away from a negative number, and similar for a number smaller than − 9.)
    Given a passcode, we define the magnitude of one of its standard differentials to be the sum of all the positive values in the differential (which is also the absolute value of the sum all the negative values).
    Claim 2: The magnitude of the a passcode’s standard differential is equal to the passcode’s complexity.
    Proof: Obviously 0000 is the only passcode with complexity 0 whose standard differential has magnitude 0. Suppose that the magnitude of a standard differential is M , then it suffices show that themagnitude can be reduced to 0 in M moves, and that the magnitude can only decrease by at most 1
    with each move.
    The first part can be shown via the following algorithm. When the magnitude is not zero, there must be a positive number d and a negative number d . WLOG assume that i < j , then after taking thei jdials a , a , . . . , a and decreases them all by 1, d decreases by 1 and d increases by 1. This willi i +1 j − 1 i jdecrease the magnitude by 1 (and the differential remains standard), so by repeating this process Mtimes we can bring the magnitude down to 0.
    For the second part, we assume WLOG that we take the dials a , a , . . . , a and decrease them alli i +1 j − 1
    ′ ′
    by 1, and then d is replaced by d = d − 1 and d = d + 1. If the differential remains standard, theni i ji jthe magnitude decreases by 1 (when d > 0 and d < 0), remains the same (when either d ≤ 0 andi j id < 0 or d > 0 and d ≥ 0), or increases by 1 (when d ≤ 0 and d ≥ 0).
    j i j i j
    In the latter two cases, it is possible that the differential is no longer standard.
    If the magnitude previously remained the same (WLOG suppose that d > 0 and d ≥ 0), then therei j
    ′
    exists a negative d that is minimal such that d − d = 10 and now d is the unique maximum.
    k j kj
    ′ ′
    Replacing d by d + 10 = d and d by d − 10 = d + 1 will reduce the magnitude by 1, and the newk k j kj j
    ′
    differential will be standard because the unique maximum d is no longer present and the minimum isjnow either d or d + 1. This means that the magnitude decreases by at most 1.
    k k
    If the magnitude previously increased by 1 (when d ≤ 0 and d ≥ 0), then there exists either a negativei jd that is (previously) minimal such that d − d = 10, or a positive d that is (previously) maximalk j k l
    ′
    such that d − d = 10, or both. By similar logic as the previous case, replacing d by d + 10 and dl i k k
    ′ ′ ′jby d − 10, or replacing d by d − 10 and d by d + 10 (or both, if both d and d exist). will decreasel l k lj i ithe magnitude by 1, and ensure that the new differential is standard. The replacement will decreasethe current magnitude by at most 2, this means that the original magnitude decreases by at most 1 intotal.
    These considerations finishes the second part and therefore the proof.
    With this claim, we also see that the magnitudes of all possible standard differentials of a given passcodeare the same, so the choice of the differential is irrelevant.
    We can now proceed to find the maximum possible complexity. Suppose that there are m positivenumbers and n negative numbers in the differential, and suppose that the maximum and the minimumare x and − y respectively. Since the sum of all positive numbers is at most mx and the absolute valueof the sum of all negative numbers is at most ny , the complexity is at most C = min( mx, ny ). Itsuffices to maximize C under the condition that m + n ≤ 5 and x + y = x − ( − y ) ≤ 10. It is notdifficult to see (via casework) that the maximal C is 12, achieved by m = 2 , n = 3 , x = 6 , y = 4 orm = 3 , n = 2 , x = 4 , y = 6. In the first case, the digits must increase from 0 by 6 twice and decreasesby 4 three times (and reduced modulo 10), which gives the passcode 6284; in the second case the digitsincrease by 4 three times and decreases by 6 twice instead, which gives the passcode 4826. Since allinequalities are tight, these two passcodes are the only ones that has the maximal complexity of 12.