HMMT 十一月 2010 · 冲刺赛 · 第 29 题

英文解析

29. [ 17 ] In the game of Galactic Dominion, players compete to amass cards, each of which is worth acertain number of points. Say you are playing a version of this game with only two kinds of cards,
    planet cards and hegemon cards. Each planet card is worth 2010 points, and each hegemon card isworth four points per planet card held. You start with no planet cards and no hegemon cards, and, oneach turn, starting at turn one, you take either a planet card or a hegemon card, whichever is worthmore points given the hand you currently hold. Define a sequence { a } for all positive integers n bysetting a to be 0 if on turn n you take a planet card and 1 if you take a hegemon card. What is thennsmallest value of N such that the sequence a , a , . . . is necessarily periodic (meaning that there is
    N N +1
    a positive integer k such that a = a for all n ≥ N )?
    n + k n
    Answer: 503 If you have P planets and H hegemons, buying a planet gives you 2010 + 4 H pointswhile buying a hegemon gives you 4 P points. Thus you buy a hegemon whenever P − H ≥ 502 . 5, andyou buy a planet whenever P − H ≤ 502 . 5. Therefore a = 1 for 1 ≤ i ≤ 503. Starting at i = 504
    (at which point you have bought 503 planets) you must alternate buying planets and hegemons. Theisequence { a } is periodic with period 2.
    i ≥ 503 i