**Homework for Combinatorics**

Mathematics 566: Fall 2003

**Homework:**
Homework is the most important part of this class.
Doing lots of homework problems is crucial for doing well in this class.
Some homework problems will help you learn the material and demonstrate
this knowledge. Other problems will involve lots of experiments and
open-ended investigation.
The process of doing homework will help you find your own way of
solving problems for the tests.
Homework is due every Friday at the beginning of class.
Late homework is only worth 50% of the total score.
Homework must be neat, legible, and stapled in order to receive credit.
I encourage you to brainstorm the problems in groups and write up your
solutions independently. Remember to explain all your work.

** HW1: due 8/29**

READ: Section 1.1 Tucker

BOOK PROBLEMS: S1.1: pages 11-16, #4,9,25 (i and iii only),36

OTHER PROBLEMS: A) Fill out the "map of the U.S." worksheet.

B) Pick 5-10 graphs (from the book, or draw your own). Count the number of
edges. Add up the degrees of all the vertices. How are these numbers related?

C) Remember that for a complete graph, there is an edge between every two
vertices. How many edges are there for a complete graph in the case that
the number v of vertices is 2,3,4, or 5? Can you find a formula that tells
how many edges there will be when the number of vertices v is large?

** HW 2: due 9/5**

Read: Sections 1.2-1.3 Tucker

Book problems: S1.2: pages 21-25, #6(a-h), 14,16; S1.3: pages 30-32, #1,6,8a,12.

Other problems: A) Pick 5-10 planar graphs (from the book, or draw your own).
Count the number of vertices, edges, and regions. (Don't forget the region outside the graph!)
Find a formula that relates these numbers.

** Quiz:** in class on Wednesday 9/10, will cover Chapter 1 of Tucker.

** HW 3: due 9/12 **

Read: Section 1.4 Tucker

Book problems: S1.4: #3(a-d, redraw the planar graphs without any edge crossings and
highlight the K33 configuration in the nonplanar graphs),

7(abc), 12(ab), 17, 27(ac).

Other problems: Bring in a map of Africa
(for example, there's one at
http://www.heather-ellis.com/africa/MapTravelsAfrica.htm)
which is colored with only 4 colors, so that
no two adjacent countries have the same color.

** HW 4: due 9/19**

Read: Appendix 2 (pages 392-393) and Sections 2.1, 2.2 Tucker

Book problems: A2 (pages 393-395) #1, #21;
S2.1: #2,9,10,16,19(a-c); S2.2: #4(c-f), 8(b), 11.

(hint for #10 in S2.1: for each square,
how many others can the knight jump to?)

** HW 5: due Friday 9/26**

Read: Sections 2.3, 2.4, 3.1 Tucker

Book problems: S2.3: 1(g-i),6,7a,8; S2.4: 2,10;
S3.1 1c, 2, 3, 10, 19, 23, 26.

Other problems:
A) Construct a map by drawing a continuous curve which begins and ends at the
same point and crosses itself as many times as you want. Determine how many
colors are needed to color this map and explain why this is true in general.

** HW 6: due 10/10 **

Read: Sections 3.2, 3.3, 4.1, 4.2 Tucker

Book problems: S3.2: 1c,2c,4, 5, 16a, 19; S3.3: 5,6,7b;
S4.1: 3(a-c), 4; S4.2:1.

** HW 7: due 10/17**

Read: Sections 5.1, 5.2, 5.3 Tucker

Book problems: S5.1: 7,9,14,18,32; S5.2: 14,22,28,55; S5.3: 2,5,7,18.

** HW 8: due 10/24**

Read: Sections 5.4, 5.5, Appendix A4 (pages 399-402) Tucker

Book problems: S5.4: 4,8,10a,44; S5.5 1b, 2a, 4b, 14c; A4: 2,4,8.

** HW 9: due 11/7**

Read: Sections 6.1, 6.2, 6.3 Tucker

Book problems: S6.1: 2a, 4b, 14; S6.2: 12,19,20,27; S6.3: 1b, 2a, 4.

** HW 10: due 11/14**

Read: Sections 7.1, 7.3 Tucker

Book problems: S7.1: 2, 4, 15, 16a; S7.3: 3ab.

Other problems: show every fourth fibonacci number is divisible by 3.

** HW11: due 11/21**

Read: Sections 7.4, 7.5 Tucker

Book problems: S 7.1: 24; S7.3: 5, S7.4: 1c, 2, 6, 9c; S7.5: 1a, 2a.

** HW12: due 12/5**

Read: Sections 8.1,8.2 Tucker

Book problems: S8.1: 2,10,14,16,22; S8.2: 2,5,22; extra credit S8.3: 8a.

** HW13 (last homework!): due 12/12**

Other problems:

1. Find a 5-by-5 magic square.

2. Find two orthogonal 5-by-5 Latin squares and solve the officer's problem when n=5.

3. Draw a complete graph on 7 vertices and color its edges so that
the edges with each color form a triangle.

How many trianges do you need?

4. A 6-by-6 chessboard is perfectly covered with 18 dominos.

Prove that it is possible to cut it either horizontally or vertically without cutting through
a domino, in other words that it has a fault line.

Do either problem 5A or 5B

5A. Construct a perfect cover of an 8-by-8 board by dominos which has no fault line.

5B. Show how to cut a cube (3 feet on an edge) into 27 unit cubes (1 foot on an edge)
using exactly 6 cuts,

but making a non-trivial arrangement of the pieces between two of the cuts.

** Info on Final**

The final covers Tucker Sections 1.1-1.4, 2.1-2.4, 3.1-3.2, 4.1-4.2, 5.1-5.5, 6.1-6.3,

7.1, 7.3-7.5,
8.1-8.2, A2, A4, and random topics from class.

At the moment, I expect the format of the final will consist of 10 short questions and 2 long questions,

but I'll update this by Monday after I've written it.

No books or notes are allowed. A calculator will not be necessary, but you can use one if you want.

If you think there is any formula or definition that you are in danger of forgetting,
send me an e-mail.

If it seems reasonable, I will put these formulae either on the board
or on the exam itself.