HMMT 二月 2011 · 冲刺赛 · 第 10 题

英文解析

10. [ 6 ] In how many ways can one fill a 4 × 4 grid with a 0 or 1 in each square such that the sum of theentries in each row, column, and long diagonal is even?
    Answer: 256
    First we name the elements of the square as follows:
    a a a a
    11 12 13 14
    a a a a
    21 22 23 24
    a a a a
    31 32 33 34
    a a a a
    41 42 43 44
    We claim that for any given values of a , a , a , a , a , a , a , and a (the + signs in the diagram
    11 12 13 21 22 23 32 33
    below), there is a unique way to assign values to the rest of the entries such that all necessary sumsare even.

• • • a + + + a 14
      a + + a 24
      31 34
      a a a a
      41 42 43 44
      Guts Round
      Taking additions mod 2, we have a = a + a + a
      14 11 12 13
      a = a + a + a
      24 21 22 23
      a = a + a + a
      44 11 22 33
      a = a + a + a
      42 12 22 32
      a = a + a + a
      43 13 23 33
      Since the 4 th column, the 4 th row, and the 1 st column must have entries that sum to 0, we have a = a + a + a = a + a + a + a + a
      34 14 24 44 12 13 21 23 33
      a = a + a + a = a + a + a + a + a
      41 42 43 44 11 12 13 23 32
      a = a + a + a = a + a + a + a + a
      31 11 21 41 12 13 21 23 32
      It is easy to check that the sum of entries in every row, column, and the main diagonal is even. Sincethere are 2 = 256 ways to assign the values to the initial 8 entries, there are exactly 256 ways to fill 8
      the board.