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

HMMT February 2011 — Guts Round — Problem 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 the entries in each row, column, and long diagonal is even?

解析

[ 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 the entries 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 sums are even.

- - a 14
- - a 24 a + + a 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 4th column, the 4th row, and the 1st 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. Since 8 there are 2 = 256 ways to assign the values to the initial 8 entries, there are exactly 256 ways to fill the board.