Start typing to search every page on this site.

Use ↑ and ↓ to move through results, then Enter to open one.

    Skip to main content

    Midterm 3 Information#

    Format and rules#

    Midterm 3 takes place on Friday, November 13, lasts 50 minutes, and has five problems. One problem consists of true-or-false questions; the others ask for computations with a short explanation.

    You may bring one handwritten study sheet or formula sheet on one A4 page, written on both sides. No other notes or outside materials may be used during the exam. You are encouraged to use an offline calculator.

    Show the method that justifies each answer. A number without supporting work may receive only partial credit. When you use Burnside’s lemma, show the cycles or the cycle count of each group element and the sum you divide.

    Coverage#

    The exam covers groups, permutations, group actions, and Burnside’s lemma: the material from Lecture 23 (groups, symmetries of polygons, and permutations) through Burnside’s lemma. It corresponds to the Groups and Group actions and Burnside’s lemma lecture notes and to Homework 8. Pólya counting and symmetries of graphs are not tested. Material from earlier units is not tested directly.

    Practice worksheets#

    These optional worksheets are not collected or graded. Together they cover every kind of problem on the exam, with different data, and each one has posted solutions that model the expected amount of explanation. Work on paper first, then check your work against the solutions.

    Topics to practice#

    You should be able to describe the symmetries of a small object as permutations, compute with them, and use them to count colorings up to symmetry. In particular, practice solving problems of the following kinds.

    • Groups: definitions and basic facts

      • State the group axioms (closure, associativity, identity, inverses).

      • Given a set with a described operation (for example composition of functions or symmetries, or addition or multiplication modulo ), decide whether it is a group: check that the operation stays inside the set, find the identity element, find the inverse of each element, and, when one of these fails, give a specific element or pair of elements that shows it. Examples that are groups include with addition modulo , the rotations , the symmetries , and the symmetric group .

      • Know the orders , , and .

      • Decide whether a subset is a subgroup; for a finite subset, check that it is closed under the operation.

      • Use Lagrange’s theorem: the order of a subgroup, and the order of an element, divide the order of the group.

    • Cyclic groups

      • Find the order of an element, in , in , or in .

      • List the elements of a cyclic subgroup , for example in .

      • Decide whether a group is cyclic.

      • Use the fact that a cyclic group is commutative: if two elements do not commute, the group is not cyclic.

    • Permutations and cycle notation

      • Convert a permutation between two-row notation and cycle notation.

      • Find the cycle type and the number of cycles , remembering that fixed points count as cycles of length .

      • Compose permutations from right to left ( means first , then ), including cycles that share elements, and check that the order of the factors matters.

      • Find the inverse of a permutation by reading each cycle backwards.

      • Find the order of a permutation.

    • Symmetries as permutations

      • Write the rotations and reflections of a square or of a regular polygon as permutations of the corners, in cycle notation.

      • Write the symmetries of a grid or a rectangle as permutations of its cells.

      • Write a rotation of a tetrahedron, a cube, or a solid like the pentagonal bipyramid of Homework 8 as a permutation of its vertices (or faces), given labels on a picture.

    • Group actions

      • Check the two rules of an action: and .

      • Move a coloring by a group element: the color at moves to . Compute for a coloring written as a string.

      • Compute an orbit by applying every group element, and compute a stabilizer and a fixed set directly from the definitions.

      • Use the orbit–stabilizer theorem to find the size of an orbit without listing it, or to find the number of elements of a group (for example the rotations of the tetrahedron and the rotations of the cube).

      • Know that the orbits split the set into disjoint classes, so the size of each orbit divides .

    • Classifying the rotations of a solid

      • Sort the rotations of a solid by their axes: through vertices, through centers of faces, through midpoints of edges.

      • Count the axes of each kind and the rotations about each axis, and check that the total is .

      • For each kind, find the cycle type of the action on the vertices, the faces, or the edges; rotations of the same kind have the same cycle type.

      • Practice on the regular tetrahedron, the cube, and the pentagonal bipyramid.

    • Burnside’s lemma

      • State Burnside’s lemma: the number of orbits is .

      • Use for colorings with colors: a coloring is fixed by exactly when it is constant on each cycle of .

      • Organize the computation in a table: kind of element, how many, , fixed colorings, and their product.

      • Count strings up to reversal, necklaces and bracelets, colorings of grids up to rotation and reflection, and colorings of the vertices or faces of a solid up to rotation.

      • Find a formula in terms of , and check it: the result must be a whole number, and must give .

    On this page