Go to announcements | course information.

on homework problems

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.

- 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. - You may discuss hand-in HW with other people, but you must write it up in your own words.
- No little stubbies from tearing a page out of your binder. Remove them neatly, please!
- 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.

Due Thurs. 9/4:

Due Fri. 9/5:

*Hand in* Fri. 9/5: Ch. 1, ## 5, 9, 10.

Due Mon. 9/8:

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

*Read* Sects. 3.1-3.3.
*Do* for discussion on

*Hand in* Mon. 9/15: Ch. 3, ## 4(c), 5(b), 12, 14.

*Read* Sects. 3.4-3.5.
*Do* for discussion on

*Hand in* **Changed to Mon. 9/22**: Ch. 3, ## 18, 20, 27, 33, 36, 38, 39(b).

*Read* Sects. 5.1, 5.2, and 5.3 to Equation (5.10) (p. 133).
*Do* for discussion on

Hand in Mon. 9/29: ## 6, 9, 10, 14, and 18.

- A1. Prove combinatorially the formula in Ch. 5, #19:
m
^{2}= 2 C(m, 2) + C(m, 1).

*For Wed. 10/8:* Read Sects. 5.3-5. (In Sect. 5.4, emphasize clutters and Sperner's Theorem 5.4.3.)
*Do* for discussion on

Hand in Mon. 10/13: ## 18, 20, 24, 32, B1, and B4.

- 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.

*For Mon. 10/13:* Read Sections 6.1-6.2.
*Do* for discussion on

Hand in Mon. 10/20: Ch. 6, ## 2, 5, and ## C2(b), C3.

- C1. 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;
- (c) the dozen must contain at least 2 maple frosted and 3 chocolate doughnuts.
- C2. Find the number of solutions to x
_{1}+ x_{2}+ x_{3}+ x_{4}= 22 in integers that satisfy

x_{1}<= 14, x_{2}<= 8, x_{3}<= 15, x_{4}<= 7, and- (a) all x
_{i}>= 0;- (b) all x
_{i}> 0.- C3. Find a formula for the number of r-combinations of the multiset

M = {infty·a_{1}, infty·a_{2}, 100·a_{3}, 100·a_{4}},

for all r >= 0. (``infty'' means infinity.)

*For Mon. 10/20:* Read Sections 6.3-6.4.
*Do* for discussion on

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

*For Mon. 10/27:* Read Section 6.5.
*Do* for discussion on

- D1. Let t be a positive integer and let M be the multiset {t·a
_{1}, t·a_{2}, ..., t·a_{k}}. 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:*Try small cases.*You may want to start with k = 3 (or even k = 2) to get an idea.

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

Do for discussion on:

Hand in Mon. 11/10:

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

Do for discussion on:

Hand in Mon. 11/17: Ch. 2, ## 3, 17, 23, 27, and # E5(c).

- E1.(a) In # 9, prove the same is true if there are 9 people in the room.
- (b) Prove that the conclusion does
*not*necessarily follow if the number of people in the room is 6.- (c) 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_{60}is true.- (a) Show that X
_{n}is true for n = 61, 62, ... for as far as you can prove it. See how high you can get! - (b) 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
_{32}= {0, ..., 31}. In the codebook of spy ``X'', some of the numbers in Z_{32}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_{32}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_{32}): 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_{32}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
^{2}+ 1 numbers. For each sequence, find m_{1}, m_{2}, ..., 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.- (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.

- E5. Find a sequence of N numbers that has no increasing and no decreasing subsequence of length n + 1, where
- (a) n = 3, N = 9;
- (b) n = 4, N = 16;
- (c) N = n
^{2}for any n >= 1.

- E6. In connection with Application 4, solve as many values of k >= 22 as you can.
- (b) Prove that the conclusion does

Read Section 2.3 (except the material on t-element subsets on pages 40-41), Section 5.6 (omit the square root of 20 on page 149), and Section 7.1.

Do for discussion on:

- Ch. 2, ## 13, 20.
- Ch. 5, # 40, also # F2(a,c).
- Ch. 7, ## 1(a,b), 2, 3(a), 6, 15(a).

- Ch. 2, # 21 (if ambitious).
- # F3(a,d).
- Ch. 7, ## 1(c), 3(c), 4, 15(d).

Hand in Mon. 11/24 **(Revised due date: Wed. 11/26 at 1:00 p.m.)**:

- Ch. 2, ## 23, 27.
- Ch. 7, ## 1(d), 3(d), 7.
- ## F1, F2(b), F3(b,c).

- F1. Does K
_{7}--> K_{4}, K_{3}? - F2. For use in the binomial series, ``evaluate'' (or ``simplify'') the binomial coefficients (r choose n) for all n > 0
s
and for:
- (a) r = -1. Try to do it both directly and via Ch. 5, # 21.
- (b) r = -k, where k is any positive integer. Again, do it both directly and via Ch. 5, # 21.
- (c) r = 1/2. (This is in the book, but you should try to do it for yourself. Hint: n = 0 and n = 1 should be treated as special cases. Maybe also n = 2.)

- F3. Substitute your answers from # F2 in the binomial series and simplify to see what you get for the following expressions:
- (a) (1-x)
^{-1}. - (b) (1-x)
^{-2}. - (c) (1-4x)
^{-1/2}(here you can use the simplified binomial coefficient I showed in class, or work it out yourself). - (d) (1-4x)
^{+1/2}(here, use the simplified binomial coefficient from F3(c)).

- (a) (1-x)

Read Section 7.4; Section 7.2 to the top of p. 204 (to learn what is a ``linear recurrence relation with constant coefficients,'' both homogeneous and nonhomogeneous).

Do for discussion on:

Hand in **Mon. 12/1** (not 12/2): Ch. 7, ## 23(e), 24(e), 31.

- G1. (Variant of Application 8) Supppose you have n colors and two disks of n sectors each, a fixed outer disk and a rotatable inner disk. You color the sectors of the outer disk so they all have different colors, and you color the sectors of the inner disk any way you like. Prove that there is a way of aligning the sectors so that at least one outer sector is lined up with an inner sector of the same color.
- G2. Prove that r(3,4) > 8 by showing that it is possible to color the line segments joining 8 points in the plane in two colors, red and blue, so that there is no red triangle (red K
_{3}) and no blue K_{4}.

Read Sections 7.5 (you will not be tested on pp. 232-234), 7.6, and 8.1.

Do for discussion on:

Hand in Thurs. 12/11: Ch. 7, ## 25(e), 33, and Ch. 8, ## 2, 4(b) (see the correction).

Due Fri. 12/12:

To read more about the many dozens of different things that Catalan numbers count, you can glance through Richard Stanley's Web page: here are links to his notes in PDF format and in PostScript format.

- H1. In Ch. 6, # 30, prove:
- The number of linear permutations of M = { 2·a, 3·b, 4·c, 5·d } equals 13!/2!3!4!5!.
- The number of linear permutations of M' = { aa, 3·b, 4·c, 5·d } equals 12!/3!4!5!. (aa is a single element composed of two a's.)
- The number of linear permutations of M'' = { aa, bbb, 4·c, 5·d } equals 10!/4!5!.

Go to announcements | course information.