HMC Math 55: Discrete Mathematics (Spring, 2002)

Assignment #13 (due Fri. 5/3):

Section 46 (pg 383): 2, 9
Section 48 (pg 399): 1, 7, 11
Section 49 (pg 409): 2, 4 (see below), 10, 11
13A: Do the proofs for the following pieces of the "equivalent conditions for trees" theorem...
(i) Prove that a graph G is a tree iff for any two vertices u, v in V(G), there exists a unique path between u and v.
(ii) Prove that if a connected graph with n vertices has n-1 edges, then it has no cycles (and hence a tree). Hint: Start deleting edges in cycles.
13B: Extend the proof from Exercise 49.4... Let G be a planar graph with n vertices and m edges, and g an integer between 3 and n (inclusive).
(i) Prove that if the smallest cycle in G has at least g edges, then m <= g(n-2)/(g-2).
(ii) Use this fact to give an alternate proof that Petersen's graph (see pg 410) is nonplanar.
(Note1: You do not need to write out a solution to Exercise 49.4 separately... simply show it to be a special case of this problem.)
(Note2: The size of the smallest cycle is known as the girth of a graph.)
Weekly thing
Some solutions for HW#13

Assignment #12 (due Fri. 4/26):

Section 44 (pg 368): 3, 4, 5, 7
Section 45 (pg 375): 6, 9
Section 47 (pg 390): 2, 3
11A: Use an extremal argument to prove that any connected graph (with at least one edge) has two vertices whose simultaneous deletion does not disconnect the graph. (Recall that deleting a vertex from a graph also requires that all its edges be deleted.)
11B: Draw an Eulerian graph with an even number of vertices (no isolated ones) and an odd number of edges, or prove that this is impossible.
Weekly thing
Some solutions for HW#12

Extra Credit (Optional) (due Fri. 4/26): I know your Discrete workload has been rather light lately, so I thought I'd give you a little something extra to work on in all that free time you must have. Please work it yourself, and do not consult others (in our class or otherwise) for assistance. Turn it in to me and do not attach it to your homework.

A Martian appears before freelance mathematicians Sam and Max and says "I am thinking of two numbers X and Y where 3 <= X <= Y <= 97. I'll tell Sam their sum, and Max their product, and then, because I have wise-ass tutors to fry, I'll be going." After he does all of this, but before the smell of burnt mathematician comes wafting in from the east, the following conversation ensues....

Sam: "You do not know what X and Y are."
Max: "That was true, Sam, but now I do."
Sam: "And now I do too, little buddy."
Max: "Sam, do you ever get the feeling you're nothing but a lame plot device?"
Determine X and Y. (Here's a hint.)

Assignment #11 (due Fri. 4/19):

Section 43 (pg 360): 2, 4, 6 , 8, 13, 16, 17
(For #6, the "7 colors" part is optional)

BONUS: Now that we have "18->(4,4)", we show that r(4,4)=18 by showing that "17->(4,4)" is false. We do this by finding a graph on 17 vertices with clique and independence numbers both equal to 3. Find such a graph. When I say find, in this case I do not mean construct. This would be rather hard (although you're welcome to try). Instead, go to the library (or anywhere else) and find it! Look up "Ramsey Theory", find a graph with this property, and attach a photocopy to your homework. You can look anywhere you like for this graph except a classmate's homework.
Weekly thing
Some solutions for HW#11

2nd Midterm: Takehome, Due Wednesday, April 17

Low Fat Assignment #10 (due Fri. 4/12):

Section 35 (pg 294): 13, 14 (then read 15 & 16)
Section 38 (pg 323): 8 (this means "Find the cosets of H")

Weekly thing
Some solutions for HW#10

Assignment #9 (due Wed. 4/10):

Section 37 (pg 315): 2, 3, 9, 11
(For #11, just give a conjecture... don't prove; but see HW#8A and #32.18)
Section 38 (pg 323): 1, 4

Some solutions for HW#9

Assignment #8 (due Wed. 4/3):

Section 33 (pg 281): 4, 14
Section 36 (pg 308): 2, 4, 9, 13, 14
(If you don't remember the notation from #36.9, see pgs 50, 63)

8C: In class, we learned two rules for filling in group tables... (1) identity row/col same as index row/col, and (2) every row and column is a permutation of G. However, these are not sufficient to guarantee that an operation table is a group, even if every element also has an inverse in the table. As an example, see the table below... all conditions that we can easily check are satisfied, yet it is not a group. Why? Not associative. Verify that this binary operation is not associate by "guess and check". (Hint: a*b*d might be a good guess).
  | e a b c d
e | e a b c d
a | a e c d b
b | b d e a c
c | c b d e a
d | d c a b e
(Actually, I can look at this table and immediately see that it is not a group. But this requires arcane, forbidden knowledge, and if I told it to you, I'd have to kill you.)
Weekly thing
Some solutions for HW#8

Assignment #7 (due Wed. 3/27):

Section 32 (pg 269): 15, 18
Section 33 (pg 281): 2abc, 3, 10
Section 35 (pg 294): 2, 12, 19
Note: See pg 292 for an idea of how to do 35.19.
7A: Using prime factorizations, prove the following:
(i) If a|bc and gcd(a, b) = 1, then a|c.
(ii) If gcd(a, b) = 1, then gcd(a^2, b^2) = 1. (a^2 means "a squared")
Weekly thing
Some solutions for HW#7

Assignment #6 (due Wed. 3/13):

Section 31 (pg 259): 1abe, 2abe, 3
Section 32 (pg 269): 4, 9abcef, 10, 13, 17, 19
6A: Rigorously prove parts (i), (ii) and (iv) of Theorem 1.1, namely that
(i) If a|b then a|bc
(ii) If a|b and b|c, then a|c
(iv) If a,b>0 and a|b, then a<=b.
6B: Use Euclid's Algorithm to find...
(i) gcd(812, 238)
(ii) Integers x, y where 812x + 238y = gcd(812, 238)
(iii) Integers x, y where 51x + 20y = 15
Weekly thing
Some solutions for HW#6

1st Midterm: Takehome, Due Wednesday, March 6
No homework due 3/6.

Assignment #5 (due Wed. 2/27):

Section 15 (pg 114): 6, 8 (Prove these combinatorially)
(Optional hint for #6: *'s & |'s)
Section 16 (pg 124): 1, 4, 5
Section 19 (pg 154): 14
5A: For each of the following "stars & bars" notations, name the corresponding multiset and the set of candidates from which it was chosen (i.e., for "**|*|", the correct answer is "<1,1,2> from {1,2,3}"... since 3 *'s indicate a size k=3 multiset and 2 |'s indicate a size n=2+1 candidate pool).
(i) | | | |*****
(ii) ***| | |**
(iii) | |*****| | |
(iv) *| |**| |**| |
(v) *|**|***|
(vi) *****

Weekly thing
Some solutions for HW#5

Assignment #4 (due Wed. 2/20):

Section 14 (pg 104): 6, 15, 18, 19
Read Section 17 (pgs 126-132)
Section 17 (pg 132): 2, 10
Section 18 (pg 145): 4, 5 (Prove 4 & 5 by induction, not the techniques of Section 18)
Section 19 (pg 154): 3bd, 8a
4A: Recall from our BIG PROOF regarding odd entries in Pascal's triangle that the identity used to prove Case III of Lemma 3 was breezed past. Well, here it is....
Give two proofs, one combinatorial and one algebraic (using our formula for "n choose k") of the following:

Section 14, #31. Your output may be in simple ASCII, and may use *'s or something similar. An equispaced font is required. This problem will be worth bonus points equal to half an assignment, and these points are independent of your score on this assignment. Please print out your picture and your source code and submit them to me directly (do not attach to Assignment #4).
Weekly thing
Some solutions for HW#4

Assignment #3 (due Wed. 2/13):

Section 6 (pg 40): 10, 12
Section 7 (pg 44): 1, 11
Section 14 (pg 104): 3, 4, 14
3A: In Poker, if a hand is garbage (no two values the same, and no straights or flushes), it's value is determined by the highest valued card in the hand. So how many distinct poker hands have the value "Ace high"? That is, the hand is garbage (5 different values, no straights or flushes), and the highest valued card in the hand is an ace? (Note: Ace has highest value of all 13 values). Hint: These hands are a subset of the garbage hands we did in class, and the counting process is very similar.

Weekly thing
Some solutions for HW#3

Assignment #2 (due Wed. 2/6):

Section 5 (pg 29): 17, 18
Section 6 (pg 40): 3, 6
Section 7 (pg 44): 8
Section 8 (pg 51): 9
Section 9 (pg 56): 1hik, 2hik, 6
Section 10 (pg 68): 3, 5, 20

Weekly thing
Some solutions for HW#2

Assignment #1 (due Wed. 1/30):

Section 1 (pg 4): 2, 3bcdf
Section 2 (pg 14): 3, 8
Section 3 (pg 22): 6, 15
Section 4 (pg 24): 3, 6
Section 5 (pg 29): 9, 11ab, 15b
Also: Read pages xvii-xxiv and 1-29 (Sections 1-5)
Weekly thing

Return to: Math 55 Main Page * Greg Levin's Page * Department of Mathematics