|
Meeting Number Three,
February 9th:
We looked at the necklace problem
again, and verified the proposed theorem that |Ox||Sx|=|G|
in that case. Note that Sx
is a subgroup of the group of symmetries G. Thus our proposed theorem is
closely related to LaGrange's Theorem, which asserts that the order of any
subgroup divides the order of the group. We looked at the proof of
LaGrange's Theorem, which actually asserts that |H|[G:H]=|G|. Here [G:H]
is a count of the number of distinct cosets of H in G. An excellent
:) presentation of this theorem can be found in Chapter 31 of Anderson
& Feil. Courtney
then treated us to some numerical and metaphysical speculations! See
you next Block! Meeting Number Two,
February 2nd:
Volunteers put their brute force
solutions for counting problems 2, 4 and 5. The
answer for Problem 2 is 21. Here are details. The
answer for Problem 4 is 11, and for Problem 5 we lose only one necklace; the
answer there is 10. We
then had another look at Problem 1 in a more general context. We can think
of the group G of symmetries of the square as acting on the set X of all sixteen
colorings (where we do not allow the checkerboard to move). This was our
first glimmer of some abstract structure. At least in this example, for
any given element x of X, we discovered empirically that the number of elements
in the orbit of x times the number of group elements in the stabilizer of x is
equal to the number of elements of the group. Here are details. Next
week: We'll see if the orbit/stabilizer result holds in other examples,
and then try our hands at proving it!
Meeting Number One, January 26th:
I introduced a list of combinatorial problems appropriate to the counting techniques we will learn this block.
Here are the problems:
How many distinct ways are there to color a 2x2 chessboard with two colors?
How many distinct ways are there to color a 2x2 chessboard with three colors?
How many distinct ways are there to color a 3x3 chessboard with two colors?
How many distinct ways are there to build a necklace with three beads, using three (or fewer) colors, assuming that the necklace cannot be flipped over?
How many distinct ways are there to build a necklace with three beads, using three (or fewer) colors, assuming that the necklace can be flipped over?
How many distinct ways are there to paint the faces of cube, with one red face, two blue faces and three green faces?
We solved problem 1 by BF&I (brute force and ignorance!), under the assumption that two patterns are the same if they can be transformed into one another by a rotation or flip ("rigid motion"). There are exactly 6 patterns.
This led us to a discussion of symmetries of a square, and more generally to the idea of permutations. (A symmetry of the square gives a permutation of the vertices of the square.) We discovered exactly 8 such symmetries: we have 4 choices for vertex number 1, but then vertex number 2 has only two choices (because adjacent vertices need to go to adjacent vertices). Then the other two vertices are determined. Using cycle notation for permutations, these are the identity (no motion), 90 degree rotation (1234), 180 degree rotation (13)(24), 270 degree rotation (1432), horizontal flip (14)(23), vertical flip (12)(34), and two diagonal flips (24) and (13).
More generally, there are 24 permutations of the numbers 1, 2, 3, 4. Notice that 16 are not possible rigid motions of the square (they would require tearing and pasting). The set of all 24 permutations is the symmetry group S4 on 4 objects.
For those new to permutations, it would be helpful to write all 24 of these permutations, using cycle notation!
Here are some permutation computations you can check (remember that we compose functions from right to left!).
(12)(34)(254)=(12534)
1 2 3 4 5 6
2 4 3 1 6 5 = (124)(56) = (241)(65)
Next week: We have reports on the problems above. Then I will present a little more theory.
|
|
