HMMT 二月 2011 · COMBGEO 赛 · 第 10 题
HMMT February 2011 — COMBGEO Round — Problem 10
题目详情
- Mike and Harry play a game on an 8 × 8 board. For some positive integer k , Mike chooses k squares and writes an M in each of them. Harry then chooses k + 1 squares and writes an H in each of them. After Harry is done, Mike wins if there is a sequence of letters forming “ HM M ” or “ M M H, ” when read either horizontally or vertically, and Harry wins otherwise. Determine the smallest value of k for which Mike has a winning strategy.
解析
- Mike and Harry play a game on an 8 × 8 board. For some positive integer k , Mike chooses k squares and writes an M in each of them. Harry then chooses k + 1 squares and writes an H in each of them. After Harry is done, Mike wins if there is a sequence of letters forming “ HM M ” or “ M M H, ” when read either horizontally or vertically, and Harry wins otherwise. Determine the smallest value of k for which Mike has a winning strategy. Answer: 16 Suppose Mike writes k M ’s. Let a be the number of squares which, if Harry writes an H in, will yield either HM M or M M H horizontally, and let b be the number of squares which, if Harry writes an H in, will yield either HM M or M M H vertically. We will show that a ≤ k and b ≤ k . Then, it will follow that there are at most a + b ≤ 2 k squares which Harry cannot write an H in. There will be at least 64 − k − 2 k = 64 − 3 k squares which Harry can write in. If 64 − 3 k ≥ k + 1, or k ≤ 15, then Harry wins. We will show that a ≤ k (that b ≤ k will follow by symmetry). Suppose there are a M ’s in row i . In i each group of 2 or more consective M ’s, Harry cannot write H to the left or right of that group, giving at most 2 forbidden squares. Hence a is at most the number of M ’s in row i . Summing over the rows i gives the desired result. Combinatorics & Geometry Individual Test Mike can win by writing 16 M ’s according to the following diagram: · · · · · · · · · M M · · M M · · M M · · M M · · · · · · · · · . · · · · · · · · · M M · · M M · · M M · · M M · · · · · · · · ·