HMMT 二月 2005 · 冲刺赛 · 第 11 题
HMMT February 2005 — Guts Round — Problem 11
题目详情
- [7] The Dingoberry Farm is a 10 mile by 10 mile square, broken up into 1 mile by 1 mile patches. 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 patches due south of it. Ann puts up a scarecrow on each of her patches that is adjacent to exactly 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?
解析
- The Dingoberry Farm is a 10 mile by 10 mile square, broken up into 1 mile by 1 mile patches. 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 patches due south of it. Ann puts up a scarecrow on each of her patches that is adjacent to exactly 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 and due south of P . So, the only way she can put a scarecrow on P is if Keith farms the patch immediately north of P and the patch immediately east of P , in which case Ann cannot farm any of the patches due north of P or due east of P . That is, Ann can only 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 scarecrow patches are in different rows and columns. Suppose that she puts up n scarecrows. The farthest south of these must be in the 10th row or above, so she farms at least 1 patch in that column; the second-farthest south must be in the 9th row above, so she farms at least 2 patches in that column; the third-farthest south must be in the 8th row or above, so she farms at least 3 patches in that column, and so forth, for a total of 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: S S S S S S S