Math 386: Combinatorics Homework Assignments

Fall 2004

General Advice
on homework problems

Besides finding the answer, 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.

Rules for hand-in homework.

1. Hand in a final draft: neat work that is well organized and not cramped. Use as much space as you need. Please also leave some extra space between problems for my comments.
2. You may discuss hand-in HW with other people, but you must write it up in your own words.
3. No little stubbies from tearing a page out of your binder. Remove them neatly, please!
4. Fasten the pages securely. Staples are best. Folding the paper over and/or tearing it is no good (not secure); paper clips don't hold well.

HOMEWORK I (8/30)

Due Wed., 9/1:
Read Sect. 1.1.
Do (for class discussion) Ch. 1, ## 1-3.

Due Thurs., 9/2:
Read Sect. 1.2.
Do Ch. 1, ## 4(a), 8, 26.

Hand in Thurs. 9/2: Ch. 1, ## 5, 9, 10.

HOMEWORK II (9/1)

Due Fri., 9/3:
Read Sects. 1.3, 1.5.
Do ## 7, 11, 12, 15, 19, 22-24.

Hand in Wed., 9/8: Ch. 1, ## 13, 16, 25, 27

HOMEWORK III (9/1,10)

Read Sects. 3.1-3.3.

Do for discussion on
Fri., 9/10: Ch. 3, ## 1-8, 10, 13.
Mon., 9/13: Ch. 3, ## 9, 11, 12, 14, 16.

Hand in Wed. 9/15: Ch. 3, ## 4(c), 5(b), 13, 15.

HOMEWORK IV (9/13)

Read for Mon., 9/20: Sects. 3.4-3.5.

Do for discussion on
Wed., 9/22: Ch. 3, ## 17, 18, 20, 27, 31.
Thurs., 9/23: Ch. 3, ## 29, 30, 36, 38, 43, 45(a).

Hand in Mon., 9/27: Ch. 3, ## 19, 26, 33, 39, 42, 44, 45(b,c).

HOMEWORK V (9/13)

Read for Mon., 9/27: Sects. 5.1, 5.2, and 5.3 to the top of p. 136.

Do for discussion on
Wed., 9/29: Ch. 5, ## 1-4, 7, 15, 16, 19.
Thurs., 9/30: Ch. 5, ## 5, 8, 17, 20, 23, and A1.

Hand in Fri., 10/1 (date corrected from handout): Ch. 5, ## 6, 9, 10, 11, 14, and 25.

Problem Set A

• A1. Prove combinatorially the formula in Ch. 5, #19: m² = 2 C(m, 2) + C(m, 1).

HOMEWORK VI (9/13)

Read for Fri., 10/1: Sect. 5.3 and Sect. 5.4 to p. 140.

Do for discussion on
Mon., 10/4: Ch. 5, ## 20, 24, 30.
Wed., 10/6: Ch. 5, ## 28, 29.

Hand in Mon., 10/4: Ch. 5, ## 18, 26.

HOMEWORK VII (10/8)

For Wed., 10/11: Read Sects. 5.4, 5.5, and 4.5. (In Sect. 5.4, emphasize clutters and Sperner's Theorem 5.4.3.)

Do for discussion on
Thurs., 10/14:
Ch. 5, ## 13, 22, 31, 34, 36, 38, 40, B1.
Ch. 4, ## 36, 37, 42, 45.
Fri., 10/15:
Ch. 5, ## 17, 23, 32, 35, B3.
Ch. 4, ## 37, 41, 43, 47.

Hand in Mon., 10/18:
Ch. 5, ## 20, 24, 33, B2, B4.
Ch. 4, ## 44, 46, 50.

Problem Set B

• B1. Give a combinatorial proof of Chapter 5, #13.
• B2. Prove Ch. 5, #22 combinatorially, assuming r, m, k are integers and r >= m >= k >= 0.
• B3. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or #B1 or Pascal's formula might suggest an idea.)
• B4. Give a combinatorial proof of the first equation in Ch. 5, #7.

HOMEWORK VII-A (10/18)

For Wed., 10/20: Read Sect. 5.7.

Do for discussion on
Thurs., 10/21 - Fri., 10/22:
Ch. 4, ## 47 (try to get it fully solved this time); 48, 54, 55.
Ch. 5, ## 35 (try to get it fully solved this time, using C1 for guidance); 47-50; C2, C3, C4.

Problem Set C

• C1. Do # 34 for n = 6 and 7. Look for a pattern using these and previous examples we've worked on.
• C2. Do # 49 for
  1. X = {3,4,5,...,15}.
  2. X = {6,7,8,...,18}.
  3. X = {13,16,17,...,26}.
• C3. Carry out the procedure of the proof of Dilworth's theorem for X = {3,4,5,...,15}, partially ordered by divisibility (as in # 49).
• C4. Carry out the procedure of the proof of 5.7.1 for the same partially ordered set as in C3.

HOMEWORK VIII

For Mon., 10/25: Read Sections 6.1-6.2. Do for discussion on
Thurs., 10/28: Ch. 6, ## 1, 3, 4, 7, and # C'1.
Fri., 10/29: Ch. 6, ## 8, 9, and # C'2(a).

Hand in Mon., 11/1: Ch. 6, ## 2, 5, and ## C'2(b), C'3.

Problem Set C'

• C'1. 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
  1. there is no further restriction;
  2. the dozen must contain every type of doughnut;
  3. the dozen must contain at least 2 maple frosted and 3 chocolate doughnuts.
• C'2. Find the number of solutions to x₁ + x₂ + x₃ + x₄ = 22 in integers that satisfy
  x₁ <= 14, x₂ <= 8, x₃ <= 15, x₄ <= 7, and
  1. all x_i >= 0;
  2. all x_i > 0.
• C'3. Find a formula for the number of r-combinations of the multiset
  M = {infty·a₁ , infty·a₂ , 100·a₃ , 100·a₄},
  for all r >= 0. (``infty'' means infinity.)

HOMEWORK IX

For Mon., 11/1: Read Sections 6.3-6.4.
Do for discussion on
Thurs. 11/4: Ch. 6, ## 11, 15-17, 24(a), 25.
Fri. 11/5: Ch. 6, ## 12, 19-21, 24(c).

Hand in Mon. 11/8: Ch. 6, ## 13, 14, 24(b), 26.

HOMEWORK SET X

For Mon. 11/8: Read Section 2.1 to Application 5 (inclusive).

Do for discussion on Thurs. 11/11:
Ch. 6, ## 23, 27, 29.
Ch. 2, ## 1 (for k <= 21 and, if you can, k = 22), 4, 5, 10, 18.

Do for discussion on Fri. 11/12:
Ch. 2, ## 1 (for k = 23), 2, 9, 16.
In #16, assume that acquaintanceship is symmetric: i.e., if A is acquainted with B, then B is acquainted with A. (This isn't always so in real life!)

Hand in Mon. 11/15:
Ch. 6, ## 28, 30.
Ch. 2, ## 6, 7, 11, 19.

HOMEWORK SET XI (11/15)

Read Sections 2.1 (to end) and 2.2. (See correction to Application 9.)

Do for discussion on:
Thurs. 11/18: Ch. 2, ## 14, 15, 17, and ## E1, E4, E6.
Fri. 11/19: ## 26, E2, E3, E5.

Hand in Mon. 11/22: Ch. 2, ## 3, 23, and 27.

Problem Set E

• E1. This concerns Ch. 2, #9.
  1. Prove the same conclusion is true if there are 9 people in the room.
  2. Prove that the conclusion does not necessarily follow if the number of people in the room is 6.
  3. Can you decide whether or not it is possible to draw the same conclusion if there are 8 people in the room? 7 people?
  
  
  
• E2. By X_n I mean the statement that, if there are 10 people whose ages lie between 1 and n, then there exist two subgroups of the 10 people, having no members in common, such that both subgroups have the same sum of ages. The problem in the book is to show that X₆₀ is true.
  1. Show that X_n is true for n = 61, 62, ... for as far as you can prove it. See how high you can get!
  2. Find a value of n (it doesn't matter how large!) for which X_n is false: that is, if the ages of the 10 people are limited to between 1 and n, it is possible to find a selection of ages such that no two subgroups have the same age sum.
  
  
• E3. Consider the set Z₃₂ = {0, ..., 31}. In the codebook of spy ``X'', some of the numbers in Z<sub>32</sub> 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 Z<sub>32</sub> 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 Z₃₂): 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 Z₃₂ 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.
  
  
• E4. Concerning Application 9, here are some sequences of N = n² + 1 numbers. For each sequence, find m₁, m₂, ..., m_N (defined in the book) and find a longest increasing subsequence. Then find a value m such that more than n different m_i'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 m_i's to find an increasing subsequence longer than n.
  1. n = 3, and the sequence is 3, -1, -pi, pi, 3.2, 1.88, 3, 0, 14, 7.
  2. n = 3, and the sequence is 5, 9, -2, 0, -1, -4, 55, 44, 22, 23.
  3. n = 3, and the sequence is 5, 9, -2, 55, -1, -4, 0, 44, 22, 23.
  
  
  
• E5. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where
  1. n = 3, N = 9;
  2. n = 4, N = 16;
  3. N = n² for any n >= 1.
  
  
  
• E6. In connection with Application 4, solve as many values of k > 22 as you can.

HOMEWORK SET XII (11/22)

Reread Sections 4.5 and 5.7. N.B. Problem Set C is above.

Do for discussion on:
Wed. 11/24: Ch. 4, ## 37, 41, 42, 45, 47, 48, 54; also Ch. 5, ## 47-49; also C2, C3, and F1.

Hand in Mon. 11/29: Ch. 4, ## 43, 55; also C4.

Problem Set F

• F1. In the proof of Dilworth's theorem, verify that (E_i union F_i) really is a chain.

HOMEWORK SET XIII (12/2)

Read for Mon., Dec. 6:

• Section 5.6 (omit the square root of 20 on page 149),
• Section 7.4,
• Section 7.1 to p. 211,
• Section 7.2 to the middle of p. 219 (to learn what is a ``linear recurrence relation with constant coefficients,'' both homogeneous and nonhomogeneous), and
• Section 7.5.

Do for discussion on:
Wed., 12/8:

## G1(a,c), G2(a,c).

Ch. 7, ## 8 (setup only; don't solve), 19(a), 28(a,c), 29(a,c), 30(a,b), 34, 35, 37.