CSTBC Exam 1
Due: June 25, 2007

This exam is open notes/open lecture and covers 
material from lectures 1-6. You are welcome to use any 
of the course material linked from the CSTBC website. 
You should not use other reference materials. If you 
have any questions, please ask me. 

1 How Many?

Let A=\left\{ 1,2,\ldots,m\right\}  and B=\left\{ 1,2,\ldots,n\right\} . 

1. What is \left|A\cup B\right|?

2. What is \left|A\cap B\right|?

3. What is \left|A-B\right|? (Warning: consider carefully the cases m\ge n 
  and m<n.)

4. What is \left|\left\{ f\,|\, f\,:\, A\to B\textrm{ is a function from }A\textrm{ to }B\right\} \right|? (Hint: first try to solve the problem for 
  some small values of m and n. For example, how many 
  functions are there if m=n=1? What about m=3 and n=2? Try some 
  more examples. Do you see a general pattern? Does 
  your guess work for all the examples you have tried? 
  Can you prove that your guess is correct?)

5. What is \left|\left\{ G\,|\, G\textrm{ is a graph with }V(G)=A\right\} \right|? (Hint: the same strategies as in part (1) 
  apply. Try to solve the problem with m=1, m=2, and m=3.)

2 Practice Problem from Lecture 2

In lecture 2, we prove that if 0\le k\le n, \binom{n}{k}=\binom{n}{n-k}. Do the practice 
problem associated with this theorem; that is, for n=5 and k=2
, explicitly write down \mathcal{A}=\left\{ A\subseteq\mathcal{U}\,|\,\left|A\right|=k\right\} , \mathcal{B}=\left\{ B\subseteq\mathcal{U}\,|\,\left|B\right|=n-k\right\} , and the bijection f\,:\,\mathcal{A}\to\mathcal{B}.

3 Injective, Surjective, Bijective

Let A,B,C be sets and let f\,:\, A\to B, g\,:\, B\to C be functions. Define the 
function h\,:\, A\to C by setting h(a)=g(f(a)) for all a\in A; in words, the function h 
maps a\in A to an element in C by first applying f to a to 
obtain an element b=f(a) in B, and then applying g to b to 
obtain an element c=g(b) in C. We call h the composition of f 
and g, and we write h=g\circ f. 

Decide whether each of the following statements are 
necessarily true, or not necessarily true (false).

1. If g is an injection, then h is an injection.

2. If g is a surjection, then h is a surjection.

3. If f is an injection and g is a surjection, then h is a 
  bijection.

4. If f is an injection and g is an injection, then h is 
  an injection.

5. If h is a bijection, then f and g are bijections.

6. If h is an injection, then f and g are injections.

7. If h is a surjection, then f and g are surjections.

4 An Equality

Give two different proofs of the following equality: 
for all n\ge0, \sum_{j=0}^{n}2^{j}=2^{n+1}-1.

1. Let \mathcal{U}=\left\{ 1,2,3,\ldots,n,n+1\right\} , let \mathcal{A}=\left\{ A\subseteq\mathcal{U}\,|\, A\ne\emptyset\right\} , and for 0\le j\le n, let \mathcal{A}_{j}=\left\{ A\subseteq\mathcal{U}\,|\,\textrm{the largest element in }A\textrm{ is }j+1\right\} . Use these sets to 
  establish the equality.

2. Prove the equality by induction on n.

5 Graphs

A graph G is connected if for each pair of vertices u and v
 in G, there is a uv-walk in G. Prove that G is connected if 
and only if for each S\subseteq V(G) with S\ne\emptyset  and S\ne V(G), there is an edge in G 
with one endpoint inside S and one endpoint outside S.

6 A Proof with an Error

The following inductive "proof" contains an error. What 
is the number of the first line in the proof that is 
incorrect? Why is it incorrect?

Theorem: If n\ge1 balls are placed into a box B and each ball 
is colored blue or yellow, then either all balls in B 
are blue or all balls in B are yellow.

Proof:

1. By induction on n.

2. Base case: If n=1, then \left|B\right|=1, so the theorem is clearly 
  true in this case.

3. Inductive Step: suppose n\ge2.

4. Let x,y\in B be two distinct balls in B.

5. Let B_{1}=B-\left\{ x\right\}  and B_{2}=B-\left\{ y\right\} . Note that \left|B_{1}\right|=\left|B_{2}\right|=n-1<n.

6. Therefore, the inductive hypothesis implies that all 
  balls in B_{1} are blue or all balls in B_{1} are yellow.

7. Similarly, the inductive hypothesis implies that all 
  balls in B_{2} are blue or all balls in B_{2} are yellow.

8. Note that the common color of all balls in B_{1} must be 
  the same as the common color of all balls in B_{2}.

9. Because B=B_{1}\cup B_{2} and the common color in B_{1} is the same as the 
  common color in B_{2}, all balls in B are blue or all balls 
  in B are yellow. 

7 Pirates

Recently, a pirate ship with 200 pirates onboard has 
captured 1000 gold coins from another vessel. The 
pirates have developed an interesting way to distribute 
their gains among themselves. Here's what happens: the 
strongest pirate on the ship proposes a distribution of 
the coins to pirates. Next, all pirates vote on the 
proposal (including the strongest pirate). If at least 
half of the pirates vote in support of the proposal, 
the coins are distributed according to the proposal and 
the process is complete. However, if more than half of 
the pirates vote to reject the proposal, they throw the 
strongest pirate overboard and the process repeats with 
the strongest of the remaining pirates offering a new 
proposal. Each pirate is perfectly logical and wishes 
to maximize the number of coins that he or she 
receives. 

What does the strongest pirate propose? Prove your 
answer is correct. (Hint: first, try to answer the 
question if there are only a small number of pirates 
onboard -- one pirate, two pirates, etc. Next, based 
upon your investigation of what happens with a small 
number of pirates, guess what is proposed if there are n (1\le n\le200
) pirates onboard. Finally, prove by induction on n that 
your guess is correct.)

8 Ramsey Theory

In lecture 6, we present a classic proof from Ramsey 
theory and define R(m,n) for each m,n\ge1. Describe how the proof 
can be modified to show that R(m,n)\le\binom{m+n}{m}. (Note: you are not asked 
to repeat the proof in full, just describe how to 
modify the proof we saw in lecture 6.)