1. Explain why the following position cannot be reached from the original configuration of the 15-puzzle.

9 11 13 15

14 12 10 8

6 4 2 B

This position is represented by the permutation written in two-row notation as

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B

1 3 5 7 9 11 13 15 14 12 10 8 6 4 2 B

In cycle notation it is (2 3 5
9 14 4 7 13 6 11 10 12
8 15).

This is a 14-cycle, hence an odd permutation.

***

How about the following?

11 10 9 8

7 6 5 4

3 2 1 B

This position is represented by the permutation written in two-row notation as

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 B

In cycle notation it is (1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9). this is a product of seven transpositions, hence as odd permutation. Therefore,the position cannot be reached.

***

2. Let H be a nonempty subset of a group G.
Prove that H is a subgroup of G if and only if H itself with the multiplication
"inherited" from G is a group. (By "inherited" is meant that if h, k
are in H, then the product hk in H is the element hk given by G's multiplication.)

***

First, suppose that H is a subgroup of
G. Then H is nonempty, so it contains an element h. So it also
contains h' and then hh' = e. And, eh = h for every
h in H, so H has an identity element, the e
from G. Inverses: if h is in H, then
the inverse h' from G is in H. But
hh' = e, which is now known to be the identity in H. So
H has inverses. The multiplication in H is that given
by G, which is associative. Therefore, H is a group.

Second, suppose that H is a group under the
multiplication from G.

Then H, as a group itself, is nonempty. If h, k
are in H, then multiplying them in H gives the
element hk defined by G's multiplication. Therefore, hk
is in H. Now, H as a group has an identity f, which
is one of the elements of G. So ff = f, where ff is the
product given by G's multiplication. But fe = f in G.
So ff = fe, and by cancellation in G, f = e. So the identity
e of G is in H and serves as the identity in H.. Finally, if
h is in H, then it has an inverse k in H.
hk = e, where hk is the product given by multiplication in
G. But if h' is the inverse of h in G, the
hh' = e. So both k and h' are inverses for h in G.
So k = h' and h' is in H. Therefore, H is
a subgroup of G.

***

3. Let G be a group and let g be any fixed element in G. Define a function f from G into G by

"h in G, f(h) = g'hg.

Prove that f is an isomorphism
of G onto G. (An isomorphism of a group G onto itself is usually called
an **automorphism** of G. This particular automorphism is usually called
conjugation by g.)

***

one-to-one: Let f(h)
= g'hg =
f(k) = g'kg. Cancel g'
on the left and g on the right to get h = k.

onto: If h is any element of G, then f(ghg') = g'ghg'g = h.

the multiplication condition: f(h)f(k)
= (g'hg)(g'kg) = g'hkg = f(hk).

***

4. Let S_{6 }denote
the group of all permutations of the set {1, 2, 3, 4, 5, 6}.

Let g = (1 4 5 3). Calculate g'hg for the following permutations
h.

(a) h = (2 6 4)

*** (2 6 5) ***

(b) h = (2 6 5)

*** (2 6 3) ***

(c) h = (2 6 1)

*** (2 6 4) ***

(d) h = (2 4 5)

*** (2 5 3) ***

(e) h = (2 5 4)

*** (2 3 5) ***

(f) h = (3 4 1 2 6 5)

*** (1 5 4 2 6 3) ***

(g) h = (6 2)(4 5)

*** (6 2)(5 3) ***

(h) Formulate a general rule which encompasses these
calculations. State it carefully, as if you were writing it for inclusion
in a textbook.

***In a representation of h as a product
of cycles, replace each symbol by its image under g.

***

5. Textbook p. 206, #3

***on acetate 61.0***

6. Textbook, p.206 #1 modified. Instead of showing
that this system forms a semigroup, show that it does *not* form a
group.

***To be a group the system would have to be associative,
there would be an identity, and each element would need an inverse.

First, try to see if there is an identity. If
n is the identity, then the minimum of n and any
k would be k. So the min of n and 5 would be
5. So, n could not be less thatn 5 and would have to be 5 itself.
Now that we've identified the only candidate, 5, for the identity, we look
for inverses. The element 1 has to have an inverse, say,
m. But the min of 1 and m would be
1, which is not equal to 5, our only candidate for the identity.
Therefore, no inverses. Therefore not a group.

***