Homework Solution 8 PDF

Preview

Summary

MATH 3005 Homework Solution Han-Bom MoonHomework 8 SolutionChapter 29. Determine the number of ways in which the four corners of a square can be col- ored with two colors. (It is permissible to use a single color on all four corners.) LetSbe the set of all colorings before the identification. To col...

Description

MATH 3005 Homework Solution

Han-Bom Moon

Homework 8 Solution Chapter 29.

1. Determine the number of ways in which the four corners of a square can be colored with two colors. (It is permissible to use a single color on all four corners.) Let S be the set of all colorings before the identification. To color the square with two colors (say A and B), it suffices to indicate vertices with color A. So |S| = 24 = 16. The symmetry group D4 of the square permutes elements of S . For id ∈ D4 , fix(id) = S so |fix(id)| = 16. For R90◦ , a coloring in fix(R90◦ ) is a coloring with only one color. So |fix(R90◦ )| = 2. By the same reason, |fix(R90◦ )| = 2. For R180◦ , two opposite vertices are moved to each other. So a coloring in fix(R180◦ ) assigns the same color for two non-adjacent vertices. So |fix(R180◦ )| = 22 = 4. Because of a similar reason, the horizontal flip H or vertical flip V has 4 fixed points set. Finally, two diagonal flips D and D′ fix two vertices on the axis and move remaining vertices to each other. Therefore if one colors three vertices then the others are determined. Therefore |fix(D)| = |fix(D′ )| = 23 = 8. In summary, by Burnside’s theorem, 1 48 =6 (16 + 2 + 4 + 2 + 4 + 4 + 8 + 8) = 8 |D4 | and there are 6 ways to color. 2. Determine the number of different necklaces that can be made using 13 white beads and 3 black beads.   Let S be the set of all necklaces before the identification. Then |S| = 163 = 560, because it is sufficient to choose the positions of three black beads. In this case, the symmetry group D16 permutes elements of S . For id ∈ D16 , |fix(id)| = |S| = 560. Let R be any nontrivial rotation in D16 . The rotations of D16 (including id) form a subgroup of D16 isomorphic to Z16 . Note that R permutes 16 beads. For an arrangement fixed by R, if x is a black bead, then R(x), R2 (x) = R(R(x)), R3 (x) = R(R(R(x))), · · · are all black beads. In other words, orbhRi (x) = {Ri (x)|Ri ∈ hRi} are all black beads. But |orbhRi (x)|||hRi|, |hRi|||Z16 | = 16, so the number of black beads is a divisor of 16. But there are only 3 black beads, so it is impossible and |fix(R)| = 0.

1

MATH 3005 Homework Solution

Han-Bom Moon

There are two types of reflections: eight reflections have axes pass through two points, and the other eight reflections have axes pass through no points. For a reflection A of the first type, to make a fixed necklace, we need to choose a black bead on the axis and a pair of black beads off the axis. So there are 2 × 7 = 14 fixed necklaces. For a reflection B of the second type, there is no fixed necklace because the number of black beads must be even. In summary, we have 672 1 (560 + 15 · 0 + 8 · 14 + 8 · 0) = = 21. |D16 | 32 3. Determine the number of ways in which the vertices of an equilateral triangle can be colored with five colors so that at least two colors are used. Let S be the set of all colorings satisfying given conditions. Then |S| = 53 − 5 = 120 because we need to subtract 5 coloring with only one color. The symmetry group D3 permutes the elements of S . For id ∈ D3 , |fix(id)| = |S| = 120. For two rotations R120◦ , R240◦ , a fixed coloring must have the same color for all of its vertices. But such a coloring is not an element of S, |fix(R120◦ )| = |fix(R240◦ )| = 0. For three reflections, to make a fixed coloring, we need to choose a color for the vertex on the reflection axis, and another color for two vertices off the axis. Note that the color for the vertices off the axis must be different from that of the vertex on the axis. So there are 5 × 4 = 20 choices. In summary,

180 1 (120 + 0 + 0 + 20 + 20 + 20) = = 30. |D3 | 6

7. Determine the number of ways in which the edges of a square can be colored with six colors so that no color is used on more than one edge. Let S be the set of all such colorings, before the identification. Then |S| = 6 × 5 × 4 × 3 = 360. The symmetry group D4 of the square permutes the elements of S . For id ∈ D4 , |fix(id)| = |S| = 360. For any non-trivial σ ∈ D4 , there is no fixed coloring because each edge must have a different color. Therefore

360 1 = 45, (360 + 7 · 0) = 8 |D4 |

and there are 45 colorings. 10. Determine the number of ways in which the faces of a cube can be colored with three colors. Let S be the set of all such coloring before the identification. Then |S| = 36 = 729. The symmetry group of the cube, which is S4 , permutes the elements of S . 2

MATH 3005 Homework Solution

Han-Bom Moon

For id ∈ S4 , |fix(id)| = |S| = 729. For a rotation R90◦ or R270◦ along an axis which is perpendicular to two opposite faces, there are three choices of colors, for two faces intersecting the axis and for all faces off the axis. Note that all faces off the axis must have the same color. So |fix(R90◦ )| = |fix(R270◦ )| = 33 = 27. There are 6 such rotations. For a rotation R180◦ along an axis which is perpendicular to two opposite faces, there are four choices of colors, for two faces intersecting the axis and for two pairs of faces off the axis. So |fix(R180◦ )| = 34 = 81. There are 3 such rotations. For a rotation S120◦ or S240◦ along a longest diagonal (which contains two vertices), three faces containing a vertex on the axis must share the same color. So there are two choices of colors and |fix(S120◦ )| = |fix(S240◦ )| = 32 = 9. There are 2 × 4 = 8 such rotations. For a rotation T180◦ along a diagonal connecting two midpoints of the opposite edge, we have three choices of colors. So |fix(T180◦ )| = 33 = 27. There are 6 such rotations. In summary, we have 1368 1 (729 + 6 · 27 + 3 · 81 + 8 · 9 + 6 · 27) = = 57. |S4 | 24 12. How many ways can the five points of a five-pointed crown be painted if three colors of paint are available? Let S be the set of all such colorings. Then |S| = 35 = 243. The rotation group G ≈ Z5 permutes the elements of S. For id ∈ Z5 , |fix(id)| = |S| = 243. For any non-trivial rotation R, |R| = 5 and for any point x, x, R(x), R2 (x), R3 (x), R4 (x) are distinct points. Therefore for any fixed coloring, all points must be colored with the same color. Therefore |fix(R)| = 3. By Burnside’s theorem, 255 1 (243 + 3 + 3 + 3 + 3) = = 51. |Z5 | 5

3...