返回题库

HMMT 二月 2018 · 团队赛 · 第 1 题

HMMT February 2018 — Team Round — Problem 1

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 20 ] In an n × n square array of 1 × 1 cells, at least one cell is colored pink. Show that you can alwaysdivide the square into rectangles along cell borders such that each rectangle contains exactly one pinkcell.
解析

英文解析

  1. [ 20 ] In an n × n square array of 1 × 1 cells, at least one cell is colored pink. Show that you can alwaysdivide the square into rectangles along cell borders such that each rectangle contains exactly one pinkcell.
    Proposed by: Kevin Sun
    We claim that the statement is true for arbitrary rectangles. We proceed by induction on the numberof 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 containsat least one marked cell. By induction, we can divide the two smaller rectangles into rectangles withexactly one marked cell. Combining these two sets of rectangles gives a way to divide our originalrectangle into rectangles with exactly one marked cell, completing the induction.