Besides finding the anwer, always try to explain, as well as you can, how you know you have the correct answer.
When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)
Allow 15 minutes per problem (minimum) before you give up, even if you feel you're getting nowhere. These problems need time for thought. If you're still stuck, go on to another problem. Return to the sticky problem later (say, the next day). Often, it then looks easier because you tried hard the first time and then gave your mind time to grind it up--I mean, to come up with ideas. To get the advantage of this method, you have to start the problems well ahead of time. Last-minute effort will not work well in this class.
I reserve the right to reduce grades for not following these rules, especially (2).
Due Fri. 1/23:
Due Mon. 1/26:
HAND IN Tues. 1/27: Ch. 1, ## 5, 9, 10.
Due Wed. 1/28:
Due Fri. 1/30:
Hand in Mon. 2/2: Ch. 1, ## 13, 16, 25, 27
Read Sects. 3.1-3.3.
Do for discussion on
Hand in Fri. 2/6: Ch. 3, ## 4(c), 5(b), 12, 14.
Read Sects. 3.4-3.5.
Do for discussion on
Hand in Fri. 2/13: Ch. 3, ## 18, 20, 27, 33, 36, 38.
Read Sects. 5.1, 5.2, and 5.3 to (5.10).
Do for discussion on
Hand in Fri. 2/27: Ch. 5, ## 6,8, 9, 11, 12, 16, and A3.
A1. Give a combinatorial proof that
A2. Prove combinatorially the formula in Ch. 5, #17:
A3. Give a combinatorial proof of Chapter 5, #11.
Read Sects. 5.3, 5.4, and 5.5. (In Sect. 5.4, stress clutters and Sperner's Theorem 5.4.3.)
Do for discussion on
Hand in Fri. 3/6: Ch. 5, ## 18, 22, 29, and B3.
B1. Prove Ch. 5, #20 combinatorially, assuming r, m, k are integers and r >= m >= k >= 0.
B2. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of A1 or A2 or Pascal's formula might suggest an idea.)
B3. Give a combinatorial proof of the first equaton in Ch. 5, #7.
Read Section 2.1.
Do for discussion on:
Hand in Tues. 3/10: Ch. 2 ## 3, 6, 11, 17, 19, and # C2.
C1. Find a simple formula for the value of the binomial coefficient (-1 choose n), where n is a nonnegative integer.
C2. (a) A shepherd has 125 sheep and 5 dogs. How many ways are there to bundle the shorn fleece?
See announcements for corrections, definitions, and the rules of Floyd's solitaire game.
Read Section 2.2 for Wed. 3/25.
Do for discussion on:
Hand in Fri. 3/27: Ch. 2 ## 15, 19(b, c).
D1. (a) In # 9, prove the same is true if there are 9 people in the room.
D2. Consider the set Z32 = {0, ..., 31}. In the codebook of X, some of the numbers in Z32 are colored red, some of them are black, but of course you don't know which ones; you don't even know how many are red. Let's suppose you color Z32 with red and black; call your coloring "good" if your colors agree with X's on at least half the numbers. Here's a way to get a new coloring from an old one, called "shifting (to the left) by c" (where c is in Z32): the shifted color of a is the original color of a + c (if a+c >= 32, then you take the remainder after division by 32). For instance, if you color 1, 7 red and the rest black, and shift by 3, then in the shifted coloring 4 is red and so is 30 (since 7 = 4 + 3 is red and 30 + 3 = 33 reduces to 1, which is red, upon division by 32). Prove that if you color the numbers in Z32 so half are red and half black, then there is a number c (but we don't know what it is) such that your coloring shifted by c is good.
D3. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where (a) n = 4, N = 9; (b) n = 5, N = 16, (c) N = n2 for any n >= 1.
D4. Here are four permutations of {1, 2, ..., 10}. Think of a permutation as a deck of 10 cards. Your task is to play Floyd's solitaire game for each permutation. Use the leftmost-pile rule. Play it twice: once with the normal rule of play, the second time with the reverse rule. Record the piles you get (in the order the cards appear from bottom to top). (If you want to try other decks, too, go right ahead. I'll be interested in any results you come up with.)
D5. Consider permutations of any length N, i.e., permutations of {1, 2, ..., N}. Suppose that lD = 1. What can lI be? What can the permutation be, if lD = 1? You might start by checking small values of N to see what happens (the usual advice -- for good reason).
Read Section 2.3.
Do for discussion on:
Hand in Fri. 4/3: Ch. 2 ## 23, 27, E2, E4.
E1. Concerning Application 9, here are some sequences of N = n2 + 1 numbers. For each sequence, find m1, m2, ..., mN and find a longest increasing subsequence. Then find a value m such that more than n different mi's equal m, if such an m exists. If m exists, use it to find a decreasing subsequence longer than n. If no m exists, use the mi's to find an increasing subsequence longer than n.
(a) n = 3, and the sequence is 3, -1, -pi, pi, 3.2, 1.88, 3, 0, 14, 7.
(b) n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.
(c) n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.
*E2. Prove that lI lD >= N for any sequence of N numbers, where N > 0. (See definitions in the announcements. Hint: Use the method of proof in Application 9.)
E3. Prove for permutations of {1, 2, ..., N}, where N > 0, that:
(a) lI >= ceiling(N/lD).
(b) lI can actually equal ceiling(N/lD).
Hints: Do it first for lD = 1, then 2, then 3, then general lD >= 1. For each value of lD, look at small values of N first (the usual hint!). It's not necessary to solve (a) in order to do (b).
E4. For permutations of {1, 2, ..., N}, where N > 0:
(a) Prove that lI + lD <= N + 1.
(b) Show that lI can equal N + 1 - lD.
Same hints as for E3.
E5. For permutations of {1, 2, ..., N}, where N > 0:
(a) Show that, when lD = 2, lI can be equal to any number allowed by E3(a) and E4(a), i.e., any number from ceiling(N/2) to N - 1.
(b) Show that a similar fact is true for lD = 3: that is, lI can equal any number from ceiling(N/3) to N - 2.
*(c) Generalize to all lD >= 1. If you can do this, you should be able to prove:
Theorem. The pair (lI, lD) can be any pair of positive integers that satisfies lI + lD <= N + 1 and lI lD >= N.
Read Sections 6.1, 6.2.
Do for discussion on:
Hand in Thurs. 4/9 by 5 p.m.: Ch. 6, ## 2, 5, and ## F2, F4, F5.
F1. We can prove that Kp does not arrow K3, K3 by producing a coloring of the pairs using red and blue such that there is no all red or all blue triangle. How many such colorings are there? If two colorings are different only because the points are labelled differently, we'd count them as the same (technically, ``isomorphic''). So, how many are there that are really different, i.e., not just by renaming the points? Solve this for
(a) 3 points, (b) 4 points, (c) 5 points.
F2. In Ch. 2, # 22, we have a formula for finding an upper bound on Rk = r(3, ..., 3) (k 3's). That means a number nk such that Rk <= nk. Since we don't know the exact value of Rk (with only a couple of exceptions), it's useful to have such an upper bound. Using Ch. 2, # 22, find an upper bound on Rk for small k (say, k = 2, 3, 4, 5, 6 at least), and look for a general formula for an upper bound for all k.
F3. Find the number of different ways you could get one dozen doughnuts at the bakery of Ch. 6, # 6, if the bakery has 9 apple-filled, 8 maple frosted, 5 chocolate, and 7 plain doughnuts, and
(a) there is no further restriction;
(b) the dozen must contain every type of doughnut.
F4. Find the number of solutions to x1 + x2 + x3 + x4 = 22 in integers that satisfy x1 <= 14, x2 <= 8, x3 <= 15, x4 <= 7, and
(a) all xi >= 0;
(b) all xi > 0.
F5. Find a formula for the number of r-combinations of the multiset M = {(infinity)·a1, (infinity)·a2, 100·a3, 100·a4}, for all r >= 0.
Read Sections 6.3, 6.4.
Do for discussion on:
Hand in Fri. 4/17: Ch. 6, ## 13, 14, 25(b), 27.
G1. Let t be a positive integer and let M be the multiset {t·a1, t·a2, ..., t·ak}. Find a formula for the number of r-combinations of M when:
(a) r = 2t.
(b) r = 2t + 1.
(c) r = 2t - 1.
Remember the Standard Hint: You may want to start with k = 3 (or even k = 2) to get an idea.
See announcements for corrections.
Read Section 10.1 to the end of page 347.
Do for discussion on:
Hand in Mon. 4/27: Ch. 10, ## 3, 8, 11, 12, 14-15(iii), and H2.
H1. Use Ch. 10 # 1 to find
(a) the additive inverse ("negative") of every element of Z4 (i.e., arithmetic mod 4);
(b) the multiplicative inverse ("reciprocal") of every element of Z4 that has a reciprocal.
H2. Use Ch. 10 # 3 to do the same as in # H1 for Z5 (i.e., arithmetic mod 5).
See announcements for definitions about modular arithmetic and finite fields.
Read Section 10.1, pp. 348-350.
Do for discussion on:
Hand in Fri. 5/1: Ch. 10, ## 13, 17(ii, v, vi), and I3(c-f).
I1. This problem concerns the field F9 of 9 elements, with modulus polynomial f(x) = x2 + x + 2, as in the lecture.
(a) Write out the 9 elements of F9. Write the addition and multiplication tables.
(b) Find the negatives (additive inverses) and reciprocals (multiplicative inverses) of all elements that have them. Which inverses don't exist?
I2. Find another possible modulus polynomial g(x) for F9. That is, g(x) should be a polynomial of degree 2 whose coefficients are in Z3 and which is irreducible. (Also, make it monic--the coefficient of x2 is 1--to avoid trivialities.)
I3. This problem concerns the field F25. Let f(x) = x2 + x + 1.
(a) Show that f(x) is irreducible mod 5 (that is, with coefficients in Z5).
(b) List 13 of the elements of F25.
(c)-(f) Calculate in F25 with modulus polynomial f(x):
(c) (i-1) - (3i-1)
(d) (i+1) (3i-1)
(e) (i+1)/(3i-1)
(f) (i-1)-1
See announcements for corrections.
Read Section 10.4 to the top of p. 384.
Do for discussion on:
Hand in Wed. 5/6: Ch. 10, ## 41, 45, 48, and # J2.
J1. Using g(x) from # I2 as the modulus polynomial, write the elements of F9 and the + and × tables. Compare with # I1(a): are the rules of addition the same? the rules of multiplication? Do you understand why? (By the way, the fields you get with modulus polynomials f(x) and g(x), although they look different, are actually the same but with the names changed. It's a challenge, one you can solve with effort if you're inclined to try it, to figure out how the second one should have its elements renamed so as to have the same arithmetic as the first.)
J2. (a) Construct 3 MOLS of order 9.
(b) For (a) you have to use the finite field F9 of order 9. Why can you not use the product-square construction of pp. 380-382, and why could you use it to find 2 MOLS?