PROBLEMS ON ABSTRACT ALGEBRA 1 (Putnam 1972 A2).
Let S be a set and let ∗ be a binary operation on S satisfying the laws x ∗ (x ∗ y) = y for all x, y in S, (y ∗ x) ∗ x = y for all x, y in S.
Show that ∗ is commutative but not necessarily associative.
2 (Putnam 1972 B3). Let A and B be two elements in a group such that ABA = BA2B, A3 = 1 and B2n−1 = 1 for some positive integer n. Prove B = 1.
3 (Putnam 2007 A5). Suppose that a finite group has exactly n elements of order p, where p is a prime. Prove that either n = 0 or p divides n + 1.
4 (Putnam 2011 A6). Let G be an abelian group with n elements, and let {g1 = e, g2, . . . , gk} ⊊ G be a (not necessarily minimal) set of distinct generators of G. A special die, which randomly selects one of the elements g1, g2, . . . , gk with equal probability, is rolled m times and the selected elements are multiplied to produce an element g ∈ G. Prove that there exists a real number b ∈ (0, 1) such that �� �2 1 1 lim Prob(g = x) − m→∞ b2m n x∈G is positive and finite.
5 (Putnam 1990 B4). Let G be a finite group of order n generated by a and b. Prove or disprove: there is a sequence g1, g2, g3, . . . , g2n such that (a) every element of G occurs exactly twice, and (b) gi+1 equals gia or gib for i = 1, 2, . . . , 2n. (Interpret g2n+1 as g1.)
6 (Putnam 2016 A5). Suppose that G is a finite group generated by the two elements g and h, where the order of g is odd. Show that every element of G can be written in the form m1 hn1 m2 hn2 mr hnr g g · · · g with 1 ≤ r ≤ |G| and mn, n1, m2, n2, . . . , mr, nr ∈ {1, −1}. (Here |G| is the number of elements of G.)
7 (Putnam 1977 B6). Let H be a subgroup with h elements in a group G. Suppose that G has an element a such that for all x in H, (xa)3 = 1, the identity. In G, let P be the subset of all products x1ax2a · · · xna, with n a positive integer and the xi’s in H. (a) Show that P is a finite set. (b) Show that, in fact, P has no more than 3h2 elements.
8 (Putnam 1984 B3). Prove or disprove the following statement: If F is a finite set with two or more elements, then there exists a binary operation ∗ on F such that for all x, y, z in F, 1 (i) x ∗ z = y ∗ z implies x = y (right cancellation holds), and (ii) x ∗ (y ∗ z) =∕ (x ∗ y) ∗ z (no case of associativity holds).
9 (Putnam 1987 B6). Let F be the field of p2 elements where p is an odd prime. Suppose S is a set of (p2 − 1)/2 distinct nonzero elements of F with the property that for each a =∕ 0 in F, exactly one of a and −a is in S. Let N be the number of elements in the intersection S ∩ {2a : a ∈ S}. Prove that N is even.
10 (Putnam 1989 B2). Let S be a nonempty set with an associative operation that is left and right cancellative (xy = xz implies y = z, and yx = zx implies y = z). Assume that for every a in S the n set {a : n = 1, 2, 3, . . . } is finite. Must S be a group?
11 (Putnam 1992 B6). Let M be a set of real n × n matrices such that (i) I ∈ M, where I is the n × n identity matrix; (ii) if A ∈ M and B ∈ M, then either AB ∈ M or −AB ∈ M, but not both; (iii) if A ∈ M and B ∈ M, then either AB = BA or AB = −BA; (iv) if A ∈ M and A ∈/ I, there is at least one B ∈ M such that AB = −BA. Prove that M contains at most n2 matrices.
12 (Putnam 1996 A4). Let S be a set of ordered triples (a, b, c) of distinct elements of a finite set A. Suppose that (1) (a, b, c) ∈ S if and only if (b, c, a) ∈ S; (2) (a, b, c) ∈ S if and only if (c, b, a) ∈/ S [for a, b, c distinct]; (3) (a, b, c) and (c, d, a) are both in S if and only if (b, c, d) and (d, a, b) are both in S. Prove that there exists a one-to-one function g from A to R such that g(a) < g(b) < g(c) implies (a, b, c) ∈ S.
13 (Putnam 2008 A6). Prove that there exists a constant c > 0 such that in every nontrivial finite group G there exists a sequence of length at most c ln |G| with the property that each element of G equals the product of some subsequence. (The elements of G in the sequence are not required to be distinct. A subsequence of a sequence is obtained by selecting some of the terms, not necessarily consecutive, without reordering them; for example, 4, 4, 2 is a subsequence of 2, 4, 6, 4, 2, but 2, 2, 4 is not.)
14 (Putnam 2009 A5). Is there a finite abelian group G such that the product of the orders of all its elements is 22009?
15 (Putname 2010 A5). Let G be a group, with operation ∗. Suppose that 1. G is a subset of R3 (but ∗ need not be related to addition of vectors); 2. For each a, b ∈ G, either a × b = a ∗ b or a × b = 0 (or both), where × is the usual cross product in R3. Prove that a × b = 0 for all a, b ∈ G. 2
16. Let R be a noncommutative ring with identity. Suppose that x, y are elements of R such that 1 − xy and 1 − yx are invertible. (By the previous problem it suffice to assume that only 1 − xy is invertible, but this is irrelevant.) Show that (1 + x)(1 − yx) −1(1 + y) = (1 + y)(1 − xy) −1(1 + x). (1) This problem illustrates that “noncommutative high school algebra” is a lot harder than ordinary (commutative) high school algebra. Note. Formally we have (1 − yx) −1 = 1 + yx + yxyx + yxyxyx + · · · and similarly for (1−xy)−1. Thus both sides of (1) are formally equal to the sum of all “alternating words” (products of x’s and y’s with no two x’s or y’s appearing consecutively). This makes the identity (1) plausible, but our formal argument is not a proof.
17. Let G be a group of order 4n + 2, n ≥ 1. Prove that G is not a simple group, i.e., G has a proper normal subgroup.
18. Let R satisfy all the axioms of a ring except commutativity of addition. Show that ax + by = by + ax for all a, b, x, y ∈ R.
19. Let G denote the set of all infinite sequences (a1, a2, . . .) of integers ai. We can add elements of G coordinate-wise, i.e., (a1, a2, . . .) + (b1, b2, . . .) = (a1 + b1, a2 + b2, . . .). Let Z denote the set of integers. Suppose f : → Z is a function satisfying f(x + y) = f(x) + f(y) for all x, y ∈ G. Let ei be the element of G with a 1 in position i and 0’s elsewhere. (a) Suppose that f(ei) = 0 for all i. Show that f(x) = 0 for all x ∈ G. (b) Show that f(ei) = 0 for all but finitely many i.
20. Let G be a finite group, and set f(G) = #{(u, v) ∈ G × G : uv = vu}. Find a formula for f(G) in terms of the order of G and the number k(G) of conjugacy classes of G. (Two elements x, y ∈ G are conjugate if y = axa−1 for some a ∈ G. Conjugacy is an equivalence relation whose equivalence classes are called conjugacy classes.)
21 (difficult). Let n be an odd positive integer. Show that the number of ways to write the identity permutation ι of 1, 2, . . . , n as a product uvw = ι of three n-cycles is 2(n − 1)!2/(n + 1).
22. Let G be any finite group, and let w ∈ G. Find the number of pairs (u, v) ∈ G × G satisfying 2 w = uvu vuv.
23. Show that the number of ways to write the cycle (1, 2, . . . , n) as a product of n−1 transpositions is nn−2. For instance, when n = 3 we have (multiplying permutations left-to-right) three ways: (1, 2, 3) = (1, 3)(2, 3) = (1, 2)(1, 3) = (2, 3)(1, 2).
24 (difficult). Let si = (i,i + 1) ∈ Sn, i.e., si is the permutation of 1, 2, . . . , n that transposes i and i+1 and fixes all other j. Let f(n) be the number of ways to write the permutation n, n−1, . . . , 1 in � �n the form si1 si2 · · · sip , where p = . For instance, 321 = s1s2s1 = s2s1s2, so f(3) = 2. Moreover, 2 f(4) = 16. Show that f(n) is the number of sequences a1, . . . , ap of n − 1 1’s, n − 2 2’s, . . . , one n − 1, such that in any prefix a1, a2, . . . , ak, the number of i + 1’s does not exceed the number of i’s. For instance, when n = 3 there are the two sequences 112 and 121. 3 Note. An explicit formula is known for f(n), but this is irrelevant here.
25 (difficult). In the notation of the previous problem, show that � i1i2 · · ·ip = p!, i1,i2,...,ip where the sum is over all sequences i1, . . . , ip for which n, n − 1, . . . , 1 = si1 si2 · · · sip . For instance, when n = 3 we get 1 · 2 · 1 + 2 · 1 · 2 = 3!. Note. The only known proofs are algebraic. It would be interesting to give a combinatorial proof.