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

HMMT November 2010 — Guts Round — Problem 29

[ 17 ] In the game of Galactic Dominion, players compete to amass cards, each of which is worth a certain 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 is Page 2 of 3 worth four points per planet card held. You start with no planet cards and no hegemon cards, and, on each turn, starting at turn one, you take either a planet card or a hegemon card, whichever is worth more points given the hand you currently hold. Define a sequence { a } for all positive integers n by n setting a to be 0 if on turn n you take a planet card and 1 if you take a hegemon card. What is the n smallest 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

解析

[ 17 ] In the game of Galactic Dominion, players compete to amass cards, each of which is worth a certain 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 is worth four points per planet card held. You start with no planet cards and no hegemon cards, and, on each turn, starting at turn one, you take either a planet card or a hegemon card, whichever is worth more points given the hand you currently hold. Define a sequence { a } for all positive integers n by n setting a to be 0 if on turn n you take a planet card and 1 if you take a hegemon card. What is the n smallest 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 points while buying a hegemon gives you 4 P points. Thus you buy a hegemon whenever P − H ≥ 502 . 5, and you buy a planet whenever P − H ≤ 502 . 5. Therefore a = 1 for 1 ≤ i ≤ 503. Starting at i = 504 i (at which point you have bought 503 planets) you must alternate buying planets and hegemons. The sequence { a } is periodic with period 2. i i ≥ 503