PUMaC 2014 · 组合（B 组） · 第 6 题

PUMaC 2014 — Combinatorics (Division B) — Problem 6

[ 6 ] Consider an orange and black coloring of a 20 × 14 square grid. Let n be the number of coloring such that every row and column has an even number of orange square. Evaluate log n . 2

解析

[ 6 ] Consider an orange and black coloring of a 20 × 14 square grid. Let n be the number of coloring such that every row and column has an even number of orange square. Evaluate log n . 2 Solution: We see that we can color the 19 × 13 subgrid in any way as we wish, and for the last row and column, we can color them to ensure the 19 row and 13 columns all have an even number of th th orange squares. For the cell at the intersection of the 20 rows and the 14 column, we see th that we should color it such that the 20 row has an even number of orange squares. This way the entire grid will have an even number of orange squares. Since we already colored it th such that the first 13 columns have even number of orange squares, natrually the 14 column will also have an even number of orange squaers. Thus the rest of the grid has exactly one coloring possible, uniquely determined by the 19 × 13 subgrid. 19 × 13 Hence n = 2 and log n = 247 . 2