Math 417 Homework 5 Solutions

The math symbols on this page seem to view best if your browser is IE.

[1] Problem #24 on p. 24. (Hint: see Example 10 on p. 16.)

First note that a $47 bet cannot be placed. If it could, then there is a solution to 7x + 9y = 47, where x and y are integers and both at least 0. Thus 7x <= 47 so x < 7 (hence 0 <= x <= 6), and 9x <= 47 so 0 <= x <= 5. For each y from 0 to 5 we check that 47 - 9y is not a multiple of 7: 47 - 9(0) = 47, 47 - 9(1) = 38, 47 - 9(2) = 29, 47 - 9(3) = 20, 47 - 9(4) = 11, 47 - 9(5) = 2. Thus there is no appropriate solution to 7x + 9y = 47, hence a $47 bet cannot be placed.

Now we show by induction that any bet of $48 or more CAN be placed. Let S be the set of all positive integers n such that there is a solution to n = 7x + 9y, where x and y are nonnegative integers. We want to show that n is in S for every integer n >= 48. Since (x, y) = (3, 3) is a solution to 7x + 9y = 48, 48 is in S. Now assume that N is in S for some N >= 48; we will show that then N+1 is in S. It then follows by induction (using Theorem 0.4) that N is in S for every n >= 48. But the fact that N is in S means that we have a solution (a, b) to 7x + 9y = N. Since N >= 48 and a >= 0 and b >= 0, it cannot be true that both a < 5 and b < 3 (since then we would have 7a + 9b <= 7(4) + 9(2) = 46, which is less than 48). Hence either a >= 5 or b >= 3. If a >= 5, then using 7(-5) + 9(4) = 1 we have 7(a - 5) + 9(b + 4) = N + 1. Thus x = a - 5 and y = b + 4 gives a solution in nonnegative integers to 7x + 9y = N + 1, which N+1 is in S if a >= 5. If instead all we know is that b >= 3, then we use 7(4) + 9(-3) = 1 to get 7(a + 4) + 9(b - 3) = N + 1, and again we see that N+1 is in S. Hence in all cases N+1 is in S, so n is in S whenever N >= 48.

Finally, here's how to do the problem using the other form of induction, Theorem 0.5. We already know that a bet of $47 can't be placed. Let S be the set of all positive integers n such that there is a solution to n = 7x + 9y, where x and y are nonnegative integers. Note that 48 through 54 are in S: 48 = 3(7) + 3(9), 49 = 7(7) + 0(9), 50 = 2(7) + 4(9), 51 = 6(7) + 1(9), 52 = 1(7) + 5(9), 53 = 5(7) + 2(9), 54 = 0(7) + 6(9). Now assume that for some integer k > 54, the integers from 48 to k-1 are all in S. Thus k-7 > 54 - 7 = 47 is in S, hence there is a solution (a, b) with x = a and y = b being nonnegative integers such that 7x + 9y = k-7. Thus (a+1, b) is a solution to 7x + 9y = k, so k is in S. This proves that every integer n >= 48 is in S, as we wished to show.
[2] Let {f₁, f₂, f₃, ...} be a sequence of integers such that f₁ > 1 and for n > 1 such that f_n > 3f_{n - 1} + 2. Use induction to prove that f_n > 3ⁿ/2 - 1 for every integer n > 0. (Indicate which form of induction you used; Theorem 0.4 or 0.5.)

Since we are given that f₁ > 1, we know f₁ > 3¹/2 - 1. Now assume that f_n > 3ⁿ/2 - 1 for some n >= 1; we want to show that f_n+1 > 3ⁿ⁺¹/2 - 1. Our result then follows by induction from Theorem 0.4. But we are given that f_n+1 > 3fⁿ + 2, hence, substituting in for f_n we see that f_n+1 > 3fⁿ + 2 > 3(3ⁿ/2 - 1) + 2 = 3ⁿ⁺¹/2 - 1, as we wanted to show.
[3] Let {f₀, f₁, f₂, f₃, ...} be a sequence of integers such that 1 < f₀ < f₁ and for n > 1 such that f_{n + 1} > f_n + f_{n - 1}. Use induction to prove that f_n > 1.6ⁿ for every integer n > -1. (Indicate which form of induction you used; Theorem 0.4 or 0.5.)

From what we are given, we see that f₀ > 1 = 1.6⁰ and f₁ > 1. But f₁ is an integer, so f₁ >= 2 > 1.6¹. Now assume that n > 1 and that f_k > 1.6^k for 0 <= k <= n. We want to show that f_n+1 > 1.6ⁿ⁺¹; then our result will follow by induction, using Theorem 0.5. But we are given that f_n+1 > f_n + f_{n - 1}, so f_n+1 > f_n + f_{n - 1} > 1.6ⁿ + 1.6^n-1 = (1.6 + 1)(1.6^n-1) > (1.6²)(1.6^n-1) = 1.6ⁿ⁺¹, as we wanted to show.
[4] Problem 40 on p. 84. [Note: Ç should be an intersection symbol, and the symbols < and > should be the symbols showing that <g> is the cyclic group generated by g.]

I claim that <m> Ç <n> is <lcm(m, n)>. Certainly lcm(m, n) is in both <m> and <n>, hence in the intersection. Now by Problem 2 on Homework 4, this means <lcm(m, n)> is a subgroup of <m> Ç <n>. To verify the reverse inclusion (and hence establish the equality <m> Ç <n> = <lcm(m, n)>), let x be an element of the intersection. Thus x is in <m>, so x is a multiple of m, and x is in <n>, so x is a multiple of n. But this means that x is a common multiple of m and n, and hence (see below) x is a multiple of lcm(m, n), so x is in <lcm(m, n)>, as we wanted to show.

[Here I show that any common multiple of m and n is a multiple of c = lcm(m, n). Let x be a common multiple of m and n. Write x = cq + r, where 0 <= r < c. Then since r = x - cq, we see that r is also a common multiple of m and n, but it is less than the least common multiple, c. Thus r can't be positive, since the least common multiple is the least positive integer which is a common multiple. Thus r = 0, so x = cq is a multiple of c.]
[5] Problem 54 on p. 85.

[Implicitly, we are assuming here that |a| and |b| are finite.] Say x is an element of <a> Ç <b>. Then x is in <a>, so <x> is a subgroup of the cyclic group <a>, so |x| = |<x>| divides |<a>| = |a|. But likewise |x| divides |b|, so |x| divides the gcd(|a|, |b|). But gcd(|a|, |b|) = 1 since |a| and |b| are relatively prime, so |x| = 1. Thus x = e. I.e., the only thing in the intersection is e, so the intersection equals {e}, as we wanted to show.
[6] Problem 4 on p. 111.

(a) The cycle decomposition for the given permutation is (1 2)(3 5 6)(4), or just (1 2)(3 5 6) if we suppress 1-cycles. The least common multiple of the lengths of the cycles is thus lcm(2, 3) = 6. Thus |(1 2)(3 5 6)| = 6.

(b) The cycle decomposition for the given permutation is (1 7 5 3)(2 6 4), so the least common multiple of the lengths of the cycles is lcm(4, 3) = 12. Thus |(1 7 5 3)(2 6 4)| = 12.
[7] Problem 8 on p. 111.

Every element x of A₁₀ can be written as a product of disjoint cycles, and |x| is the least common multiple of the lengths of those cycles. Moreover, x must be an even permutation. But given any positive integers whose sum is 10, we can easily write down disjoint cycles whose lengths are the positive integers and check to see if the permutation is even (all we need is that there are an even number of cycles of even length). Thus the maximum order among elements in A₁₀ is just the maximum least common multiple among sets of positive integers whose sum is 10 and which correspond to an even permutation. So consider a sum of positive integers whose total is 10. Let s be the largest summand in our sum.
- If L = 10, there is only one summand and the lcm is 10. But a 10-cycle is odd so although this case occurs in S₁₀, it does not occur in A₁₀.
- If L = 9, there are only two summands, 9 and 1, and the lcm is 9.
- If L = 8, there are only two cases, 8 + 2 = 10 and 8 + 1 + 1 = 10 (but this second case would correspond to an odd permutation), so the lcm is 8.
- If L = 7, there are only 3 cases, 7 + 3 = 10, 7 + 2 + 1 = 10 and 7 + 1 + 1 + 1 = 10, so the lcm is at most 21 and since a product of a 7-cycle times a 3-cycle is even, A₁₀ really does have an element of order 21.
- If L = 6, the cases are either 6 + 4 = 10, 6 + 3 + 1 = 10 or the summands other than 6 are all 2's or 1's. Thus the lcm is at most 12.
- If L = 5, the cases are either 5 + 5 = 10, 5 + 4 + 1 = 10, 5 + 3 + 2 = 10, 5 + 3 + 1 + 1 = 10, or the summands other than 5 are all 2's or 1's. Since the cases 5 + 4 + 1 = 10 and 5 + 3 + 2 = 10 correspond to odd permutations, the lcm here is at most 15 = lcm(5, 3).
- If L <= 4, every summand is either 1, 2, 3 or 4, and lcm(2, 3, 4) = 12.
Thus the largest order of an element of A₁₀ is 21; here is an even permutation of order 21: (1 2 3 4 5 6 7)(8 9 10). (In S₁₀, the same analysis leads to the greatest order being 30, such as the permutation (1 2 3 4 5)(6 7 8)(9 10) has.)