PUMaC 2015 · 组合（A 组） · 第 7 题
PUMaC 2015 — Combinatorics (Division A) — Problem 7
题目详情
- [ 7 ] The lattice points ( i, j ) for integers 0 ≤ i, j ≤ 3 are each being painted orange or black. Suppose a coloring is good if for every set of integers x , x , y , y such that 0 ≤ x < x ≤ 3 1 2 1 2 1 2 and 0 ≤ y < y ≤ 3, the points ( x , y ) , ( x , y ) , ( x , y ) , ( x , y ) are not all the same color. 1 2 1 1 1 2 2 1 2 2 How many good colorings are possible?
解析
- [ 7 ] The lattice points ( i, j ) for integer 0 ≤ i, j ≤ 3 are each being painted orange or black. Suppose a coloring is good if for every set of integers x , x , y , y such that 0 ≤ x < x ≤ 3 1 2 1 2 1 2 and 0 ≤ y < y ≤ 3, the points ( x , y ) , ( x , y ) , ( x , y ) , ( x , y ) are not all the same color. 1 2 1 1 1 2 2 1 2 2 How many good colorings are possible? A 4 × 4 square grid of lattice points ( i, j ) for 0 ≤ i, j ≤ 3 have its lattice points painted orange or black. How many colors are possible such that for every Solution: First, it is not possible for there to be two rows or columns with 3 black tiles or two rows or columns with 3 orange tiles. And by this logic, we cannot have a row or column all of the same color. So the maximum number of orange tiles is 3 + 2 + 2 + 2 = 9 and same for black. So there are 7 , 8 or 9 orange tiles. But for every valid board with 7 orange tiles, if we change all the tiles colors, we will have a valid board with 9 orange tiles. Therefore we will count how many valid boards there are with 8 orange tiles and 9 orange tiles, and the number of valid board with 7 orange tiles is the same as 9 orange tiles. Now we note that if we rearrange the rows of a valid grid, we will still end up with a valid grid. And we also know that for a valid grid, we cannot have two identical rows and hence for each valid grid, we can rearrange the 4 rows 4! = 24 different ways to get other valid grids. It is also possible to rearrange columns but we will not count those to prevent double counting. Case 1: 8 orange tiles. There are two possible arrangements of the 8 orange tiles for the rows, 3 − 2 − 2 − 1 and 2 − 2 − 2 − 2. For the first arrangement, there are 4 ways to select 3 orange tiles in a row. Then for the next two rows with both 2 tiles, they must have an orange tile where the first row had a black tile and hence there are 3 ways to choose these two rows. Then for the last row, there is only one way to place the orange tile to prevent there being a rectangle formed by 4 black tile and there will be no rectangle with black tiles or orange tiles if we choose tiles this way. So there are a total of 4 · 3 = 12 ways to select the rows and 24 ways to rearrange them. For example: o o o b o b b o b o b o b b o b Now for the 2 − 2 − 2 − 2 case, it is easy to verify that no matter how we choose two orange tiles per row, as long as the rows are distinct, we will not get any rectangles. Therefore there ) (( ) 4 2 are = 15 different ways to select the rows and 24 ways to rearrange them. 4 Case 2: 9 orange tiles. There is only one possible way to have 9 orange tiles, and that is 3 − 2 − 2 − 2. There are 4 ways to choose 3 orange tiles for the first row and then the 3 remaining rows with 2 tiles must have an orange tile where the first row had a black tile and so there is only 1 way to select these three rows up to permutation. So there are 4 ways to select the rows and again 24 ways to permute them. Therefore our answer is 15 · 24 + 12 · 24 + 4 · 24 + 4 · 24 = 35 · 24 = 840 . Author: Roy Zhao 4