HMMT 二月 2012 · TEAM2 赛 · 第 8 题
HMMT February 2012 — TEAM2 Round — Problem 8
题目详情
- [ 20 ] Alice and Bob are playing a game of Token Tag, played on an 8 × 8 chessboard. At the beginning of the game, Bob places a token for each player somewhere on the board. After this, in every round, Alice moves her token, then Bob moves his token. If at any point in a round the two tokens are on the same square, Alice immediately wins. If Alice has not won by the end of 2012 rounds, then Bob wins. (a) Suppose that a token can legally move to any orthogonally adjacent square. Show that Bob has a winning strategy for this game. (b) Suppose instead that a token can legally move to any square which shares a vertex with the square it is currently on. Show that Alice has a winning strategy for this game.
解析
- [ 20 ] Alice and Bob are playing a game of Token Tag, played on an 8 × 8 chessboard. At the beginning of the game, Bob places a token for each player on the board. After this, in every round, Alice moves her token, then Bob moves his token. If at any point in a round the two tokens are on the same square, Alice immediately wins. If Alice has not won by the end of 2012 rounds, then Bob wins. (a) Suppose that a token can legally move to any horizontally or vertically adjacent square. Show that Bob has a winning strategy for this game. (b) Suppose instead that a token can legally move to any horizontally, vertically, or diagonally adjacent square. Show that Alice has a winning strategy for this game. Answer: see below For part (a), color the checkerboard in the standard way so that half of the squares are black and the other half are white. Bob’s winning strategy is to place the two coins on the same color, so that Alice must always move her coin on to a square with the opposite color as the square containing Bob’s coin. Team B For part (b), consider any starting configuration. By considering only the column that the tokens are in, it is easy to see that Alice can get to the same column as Bob (immediately after her move) in 7 rounds. (This is just a game on a 1 × 8 chessboard.) Following this, Alice can stay on the same column as Bob each turn, while getting to the same row as him. This too also takes at most 7 rounds. Thus, Alice can catch Bob in 14 < 2012 rounds from any starting position.