HMMT 二月 2018 · 团队赛 · 第 1 题
HMMT February 2018 — Team Round — Problem 1
题目详情
- [ 20 ] In an n × n square array of 1 × 1 cells, at least one cell is colored pink. Show that you can always divide the square into rectangles along cell borders such that each rectangle contains exactly one pink cell.
解析
- [ 20 ] In an n × n square array of 1 × 1 cells, at least one cell is colored pink. Show that you can always divide the square into rectangles along cell borders such that each rectangle contains exactly one pink cell. Proposed by: Kevin Sun We claim that the statement is true for arbitrary rectangles. We proceed by induction on the number of marked cells. Our base case is k = 1 marked cell, in which case the original rectangle works. To prove it for k marked cells, we split the rectangle into two smaller rectangles, both of which contains at least one marked cell. By induction, we can divide the two smaller rectangles into rectangles with exactly one marked cell. Combining these two sets of rectangles gives a way to divide our original rectangle into rectangles with exactly one marked cell, completing the induction.