HMMT 二月 2005 · 冲刺赛 · 第 11 题

英文解析

11. The Dingoberry Farm is a 10 mile by 10 mile square, broken up into 1 mile by 1 milepatches. Each patch is farmed either by Farmer Keith or by Farmer Ann. Whenever
    Ann farms a patch, she also farms all the patches due west of it and all the patchesdue south of it. Ann puts up a scarecrow on each of her patches that is adjacent toexactly two of Keith’s patches (and nowhere else). If Ann farms a total of 30 patches,
    what is the largest number of scarecrows she could put up?
    Solution: 7
    Whenever Ann farms a patch P , she also farms all the patches due west of P anddue south of P . So, the only way she can put a scarecrow on P is if Keith farms thepatch immediately north of P and the patch immediately east of P , in which case Anncannot farm any of the patches due north of P or due east of P . That is, Ann canonly put a scarecrow on P if it is the easternmost patch she farms in its east-west row,
    and the northernmost in its north-south column. In particular, all of her scarecrowpatches are in different rows and columns. Suppose that she puts up n scarecrows.
    The farthest south of these must be in the 10 th row or above, so she farms at least 1
    patch in that column; the second-farthest south must be in the 9 th row above, so shefarms at least 2 patches in that column; the third-farthest south must be in the 8 throw or above, so she farms at least 3 patches in that column, and so forth, for a totalof at least
    1 + 2 + · · · + n = n ( n + 1) / 2
    patches. If Ann farms a total of 30 < 8 · 9 / 2 patches, then we have n < 8. On the other hand, n = 7 scarecrows are possible, as shown:
    SSSSSSS