14 Chapter 1. Groups I Proof. (i) If α = τ1 · · · τq is a factorization of α into transpositions, then Theorem 1.13 gives sgn(α) = sgn(τ1) · · · sgn(τq) = (−1)q. Thus, if sgn(α) = 1, then q must be even, and if sgn(α) = −1, then q must be odd. (ii) If α is odd, then it is a product of an odd number of transpositions (for it is not a product of an even number of such). Conversely, if α = τ1 · · · τq, where the τi are transpositions and q is odd, then sgn(α) = (−1)q = −1 hence, q is odd. Therefore, α is not even, by part (i), and so it is odd. • Example 1.15. An analysis of the 15-puzzle, as in Example 1.11, shows that a game with starting position α ∈ S16 can be won if and only if α is an even permutation that fixes = 16. For a proof of this, we refer the reader to McCoy– Janusz, Introduction to Modern Algebra, pp. 229–234 (see Exercise 1.17 on page 15). The proof in one direction is fairly clear, however. Now starts in position 16, and each move takes up, down, left, or right. Thus, the total number m of moves is u + d+ l + r, where u is the number of up moves, and so on. If is to return home, each one of these must be undone: there must be the same number of up moves as down moves (i.e., u = d) and the same number of left moves as right moves (i.e., r = l). Thus, the total number of moves is even: m = 2u + 2r. That is, if τm · · · τ1α = (1), then m is even hence, α = τ1 · · · τm (because τ −1 = τ for every transposition τ), and so α is an even permutation. Armed with this theorem, we see that if the starting position α is odd, the game starting with α cannot be won. In Example 1.11, α = (1 12 3 14 7)(2 15)(4 8)(5 10)(6 11 13)(9)( ). Now sgn(α) = (−1)16−7 = −1, so that α is an odd permutation. Therefore, it is impossible to win this game. Exercises 1.5. Give an example of functions f : X → Y and g : Y → X such that gf = 1X and fg = 1Y . 1.6. Prove that composition of functions is associative: if X f −→ Y g −→ Z h −→ W , then h(gf) = (hg)f. ∗ 1.7. Prove that the composite of two injections is an injection, and that the composite of two surjections is a surjections. Conclude that the composite of two bijections is a bijection. ∗ 1.8. (Pigeonhole Principle) (i) Let f : X → X be a function, where X is a finite set. Prove equivalence of the following statements. (a) f is an injection. (b) f is a bijection. (c) f is a surjection.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.