HMMT 二月 2011 · ALGCOMB 赛 · 第 12 题

英文解析

12. Mike and Harry play a game on an 8 × 8 board. For some positive integer k , Mike chooses k squaresand 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, ” whenread either horizontally or vertically, and Harry wins otherwise. Determine the smallest value of k forwhich Mike has a winning strategy.
    Answer: 16 Suppose Mike writes k M ’s. Let a be the number of squares which, if Harry writesan 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 andb ≤ k . Then, it will follow that there are at most a + b ≤ 2 k squares which Harry cannot write an Hin. 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 . Inieach group of 2 or more consective M ’s, Harry cannot write H to the left or right of that group, givingat most 2 forbidden squares. Hence a is at most the number of M ’s in row i . Summing over the rowsgives the desired result.i
    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 ·
    · · · · · · · ·