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

英文解析

33. [ 17 ] How many ways can you remove one tile from a 2014 × 2014 grid such that the resulting figurecan 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 anordered 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 acanonical 4 × 4 square S whose vertices are all good. Then the sides of S partition the board into ninedistinct 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 thei + jtile with coordinates ( i, j ), place the complex number ω . Note that any 1 × 3 or 3 × 1 rectangleplaced on the grid must cover three squares with sum 1 + ω + ω = 0. Now, note that the sum of the 2
    numbers on the whole 2014 × 2014 grid, including the removed tile, is
    ( )
    2013 2013 20132
    ∑ ∑ ∑
    k + l kω = ωk =0 l =0 k =0
    which can be simplified to 1 using the identity 1 + ω + ω = 0. Therefore, it is necessary that i + j ≡ 02
    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).
    Hence the answer is exactly the set of good squares, of which there are 672 = 451584.2