返回题库

HMMT 十一月 2014 · 冲刺赛 · 第 33 题

HMMT November 2014 — Guts Round — Problem 33

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [ 17 ] How many ways can you remove one tile from a 2014 × 2014 grid such that the resulting figure can be tiled by 1 × 3 and 3 × 1 rectangles? Warning: The next set of three problems will consist of estimation problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT NOVEMBER 2014, 15 NOVEMBER 2014 — GUTS ROUND Organization Team Team ID#
解析
  1. [ 17 ] How many ways can you remove one tile from a 2014 × 2014 grid such that the resulting figure can be tiled by 1 × 3 and 3 × 1 rectangles? Answer: 451584 Number the rows and columns of the grid from 0 to 2013, thereby assigning an ordered pair to each tile. We claim that a tile ( i, j ) may be selected if and only if i ≡ j ≡ 0 (mod 3); call such a square good. First, let us show that this condition is sufficient. Observe that any such square s is the corner of a canonical 4 × 4 square S whose vertices are all good. Then the sides of S partition the board into nine distinct regions. It’s easy to see that all of them can be suitably tiled. Guts Round Now we show that only good squares can be removed. Let ω be a non-real cube root of unity. In the i + j tile with coordinates ( i, j ), place the complex number ω . Note that any 1 × 3 or 3 × 1 rectangle 2 placed on the grid must cover three squares with sum 1 + ω + ω = 0. Now, note that the sum of the numbers on the whole 2014 × 2014 grid, including the removed tile, is ( ) 2 2013 2013 2013 ∑ ∑ ∑ k + l k ω = ω k =0 l =0 k =0 2 which can be simplified to 1 using the identity 1 + ω + ω = 0. Therefore, it is necessary that i + j ≡ 0 i − j i + j (mod 3). By placing the complex number ω instead of ω , the same calculations show that i − j ≡ 0 (mod 3) is necessary. This can only occur if i ≡ j ≡ 0 (mod 3). 2 Hence the answer is exactly the set of good squares, of which there are 672 = 451584.