PUMaC 2014 · 组合（A 组） · 第 3 题
PUMaC 2014 — Combinatorics (Division A) — Problem 3
题目详情
- [ 4 ] You have three colors { red, blue, green } with which you can color the faces of a regular octahedron (8 triangle sided polyhedron, which is two square based pyramids stuck together at their base), but you must do so in a way that avoids coloring adjacent pieces with the same color. How many different coloring schemes are possible? (Two coloring schemes are considered equivalent if one can be rotated to fit the other.)
解析
- [ 4 ] You have three colors { red, blue, green } with which you can color the faces of a regular octahedron (8 triangle sided polyhedron, which is two square based pyramids stuck together at their base), but you must do so in a way that avoids coloring adjacent pieces with the same color. How many different coloring schemes are possible? (Two coloring schemes are considered equivalent if one can be rotated to fit the other.) Solution: WLOG, let the (number of red pieces) ≥ (number of blue pieces) ≥ (number of green pieces). Then, we consider the subcases of when r = 4 , b = 4 , g = 0, when r = 4 , b = 3 , g = 1, when r = 4 , b = 2 , g = 2, and when r = 3 , b = 3 , g = 2. For r = 4 , b = 4 , g = 0, there is 1 possible coloring scheme. Accounting for color selection, we get 1 · 3 = 3. For r = 4 , b = 3 , g = 1, the piece opposite of the green piece must be red, because if it’s blue, then it is impossible to place four red pieces between the green piece and the blue piece without having two adjacent red pieces. There is 1 possible coloring scheme that satisfies this. Accounting for color selection, we get 1 · 6 = 6. For r = 4 , b = 2 , g = 2, the piece opposite of each green or blue piece must be red, because otherwise, then it is impossible to place four red pieces between the green piece and its opposite 2 piece without having two adjacent red pieces. There is 1 possible coloring scheme that satisfies this. Accounting for color selection, we get 1 · 3 = 3. For r = 3 , b = 3 , g = 2, we consider several subcases. Subcase 1: green is opposite green. Then there is 1 (3 when accounting for color selection) possible coloring scheme. Subcase 2: green is not opposite green. Then there are no possible coloring schemes. To show this, WLOG fix a green piece and color the opposite piece blue (or red, doesn’t matter). Then, one must fit three reds, two blues, and one green in between. The three reds must be in one of the two ”rows” that comprise the middle portion of the visual presentation structure, because otherwise there would be two red pieces that are adjacent. It must be the top row, because otherwise the topmost blue would be adjacent to another blue inevitably. But that means inevitably green must be adjacent to green, so contradiction. In total, we get 3 + 6 + 3 + 3 = 15 .