PUMaC 2015 · 团队赛 · 第 14 题
PUMaC 2015 — Team Round — Problem 14
题目详情
- [ 10 ] Marie is painting a 4 × 4 grid of identical square windows. Initially, they are all orange but she wants to paint 4 of them black. How many ways can she do this up to rotation and reflection?
解析
- [ 10 ] Marie is painting a 4 × 4 grid of identical square windows. Initially, they are all orange but she wants to paint 4 of them black. How many ways can she do this up to rotation and reflection? Solution: We use Burnside’s Lemma. For each rotation/reflection, we count up how many combinations of 4 tiles are unaffected by that rotation/reflection. Then by summing up all these values and dividing by the number of rotations and reflections, Burnside’s Lemma tells us that is the number of unique colorings/combinations. Case 1 - Identity: The identity (no rotation or reflection) is considered a rotation/reflection ( ) 16 and this clearly doesn’t affect any of the possible colorings. So there are = 1820 such 4 colorings unaffected. ◦ Case 2 - 90 Rotation: There are two such rotations (cw and ccw) and in each case, choosing a window in the bottom right 2 × 2 grid uniquely determines the position of the other 3 windows ◦ so that the resultant coloring is the same after a 90 rotation. So there are 4 such colorings. ◦ Case 3 - 180 Rotation: There is only one such rotation and similar to case 2, choosing 2 windows on the right half of the grid will uniquely determine which two windows on the left ( ) 8 ◦ side to color to make the coloring to be unaffected by a 180 rotation. So there are = 28 2 such colorings. Case 4 - Reflection parallel to sides: There are two such reflections and like case 3, choosing 2 windows on one half uniquely determines the placement of the two windows on the ( ) 8 other half. So there are = 28 such colorings again for each reflection. 2 Case 5 - Reflection along diagonals: There are two reflections for each main diagonal. Here, we see that coloring a window along the main diagonal is unaffected by the reflection (because it is reflected to itself) but coloring a non main diagonal will have another different reflection window. So we can see that we can color 0 , 2 , or 4 windows along the main diagonal. ( ) 6 If we color 0, then there are = 15 possibilities for choosing two windows on one half of 2 ( ) ( ) 4 6 the diagonal. If we color 2 windows along the diagonal, there are to color them and 2 1 ( )( ) 4 6 ways to choose the off diagonal pair so a total of = 36 different colorings. Then if we 2 1 choose all 4 windows along the main diagonal, there is only 1 way to do this. Therefore there are a total of 15 + 36 + 1 = 52 different colorings unaffected by a reflection along the diagonal. So Burnside’s lemma tells us that there are: 1 · 1820 + 2 · 4 + 1 · 28 + 2 · 28 + 2 · 52 = 252 8 7 such colorings. Author: Roy Zhao