#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass article
\begin_preamble
\usepackage{fullpage,ulem}
\pagestyle{empty}
\end_preamble
\language english
\inputencoding auto
\fontscheme default
\graphics default
\paperfontsize default
\spacing single 
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 1
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Title

CSTBC Exam 1
\newline 
Due: June 25, 2007
\layout Standard

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.
 
\layout Section

How Many?
\layout Standard

Let 
\begin_inset Formula $A=\left\{ 1,2,\ldots,m\right\} $
\end_inset 

 and 
\begin_inset Formula $B=\left\{ 1,2,\ldots,n\right\} $
\end_inset 

.
 
\layout Enumerate

What is 
\begin_inset Formula $\left|A\cup B\right|$
\end_inset 

?
\layout Enumerate

What is 
\begin_inset Formula $\left|A\cap B\right|$
\end_inset 

?
\layout Enumerate

What is 
\begin_inset Formula $\left|A-B\right|$
\end_inset 

? (Warning: consider carefully the cases 
\begin_inset Formula $m\ge n$
\end_inset 

 and 
\begin_inset Formula $m<n$
\end_inset 

.)
\layout Enumerate

What is 
\begin_inset Formula $\left|\left\{ f\,|\, f\,:\, A\to B\textrm{ is a function from }A\textrm{ to }B\right\} \right|$
\end_inset 

? (Hint: first try to solve the problem for some small values of 
\begin_inset Formula $m$
\end_inset 

 and 
\begin_inset Formula $n$
\end_inset 

.
 For example, how many functions are there if 
\begin_inset Formula $m=n=1$
\end_inset 

? What about 
\begin_inset Formula $m=3$
\end_inset 

 and 
\begin_inset Formula $n=2$
\end_inset 

? 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?)
\layout Enumerate

What is 
\begin_inset Formula $\left|\left\{ G\,|\, G\textrm{ is a graph with }V(G)=A\right\} \right|$
\end_inset 

? (Hint: the same strategies as in part (1) apply.
 Try to solve the problem with 
\begin_inset Formula $m=1$
\end_inset 

, 
\begin_inset Formula $m=2$
\end_inset 

, and 
\begin_inset Formula $m=3$
\end_inset 

.)
\layout Section

Practice Problem from Lecture 2
\layout Standard

In lecture 2, we prove that if 
\begin_inset Formula $0\le k\le n$
\end_inset 

, 
\begin_inset Formula $\binom{n}{k}=\binom{n}{n-k}$
\end_inset 

.
 Do the practice problem associated with this theorem; that is, for 
\begin_inset Formula $n=5$
\end_inset 

 and 
\begin_inset Formula $k=2$
\end_inset 

, explicitly write down 
\begin_inset Formula $\mathcal{A}=\left\{ A\subseteq\mathcal{U}\,|\,\left|A\right|=k\right\} $
\end_inset 

, 
\begin_inset Formula $\mathcal{B}=\left\{ B\subseteq\mathcal{U}\,|\,\left|B\right|=n-k\right\} $
\end_inset 

, and the bijection 
\begin_inset Formula $f\,:\,\mathcal{A}\to\mathcal{B}$
\end_inset 

.
\layout Section

Injective, Surjective, Bijective
\layout Standard

Let 
\begin_inset Formula $A,B,C$
\end_inset 

 be sets and let 
\begin_inset Formula $f\,:\, A\to B$
\end_inset 

, 
\begin_inset Formula $g\,:\, B\to C$
\end_inset 

 be functions.
 Define the function 
\begin_inset Formula $h\,:\, A\to C$
\end_inset 

 by setting 
\begin_inset Formula $h(a)=g(f(a))$
\end_inset 

 for all 
\begin_inset Formula $a\in A$
\end_inset 

; in words, the function 
\begin_inset Formula $h$
\end_inset 

 maps 
\begin_inset Formula $a\in A$
\end_inset 

 to an element in 
\begin_inset Formula $C$
\end_inset 

 by first applying 
\begin_inset Formula $f$
\end_inset 

 to 
\begin_inset Formula $a$
\end_inset 

 to obtain an element 
\begin_inset Formula $b=f(a)$
\end_inset 

 in 
\begin_inset Formula $B$
\end_inset 

, and then applying 
\begin_inset Formula $g$
\end_inset 

 to 
\begin_inset Formula $b$
\end_inset 

 to obtain an element 
\begin_inset Formula $c=g(b)$
\end_inset 

 in 
\begin_inset Formula $C$
\end_inset 

.
 We call 
\begin_inset Formula $h$
\end_inset 

 the composition of 
\begin_inset Formula $f$
\end_inset 

 and 
\begin_inset Formula $g$
\end_inset 

, and we write 
\begin_inset Formula $h=g\circ f$
\end_inset 

.
 
\layout Standard

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

If 
\begin_inset Formula $g$
\end_inset 

 is an injection, then 
\begin_inset Formula $h$
\end_inset 

 is an injection.
\layout Enumerate

If 
\begin_inset Formula $g$
\end_inset 

 is a surjection, then 
\begin_inset Formula $h$
\end_inset 

 is a surjection.
\layout Enumerate

If 
\begin_inset Formula $f$
\end_inset 

 is an injection and 
\begin_inset Formula $g$
\end_inset 

 is a surjection, then 
\begin_inset Formula $h$
\end_inset 

 is a bijection.
\layout Enumerate

If 
\begin_inset Formula $f$
\end_inset 

 is an injection and 
\begin_inset Formula $g$
\end_inset 

 is an injection, then 
\begin_inset Formula $h$
\end_inset 

 is an injection.
\layout Enumerate

If 
\begin_inset Formula $h$
\end_inset 

 is a bijection, then 
\begin_inset Formula $f$
\end_inset 

 and 
\begin_inset Formula $g$
\end_inset 

 are bijections.
\layout Enumerate

If 
\begin_inset Formula $h$
\end_inset 

 is an injection, then 
\begin_inset Formula $f$
\end_inset 

 and 
\begin_inset Formula $g$
\end_inset 

 are injections.
\layout Enumerate

If 
\begin_inset Formula $h$
\end_inset 

 is a surjection, then 
\begin_inset Formula $f$
\end_inset 

 and 
\begin_inset Formula $g$
\end_inset 

 are surjections.
\layout Section

An Equality
\layout Standard

Give two different proofs of the following equality: for all 
\begin_inset Formula $n\ge0$
\end_inset 

, 
\begin_inset Formula $\sum_{j=0}^{n}2^{j}=2^{n+1}-1$
\end_inset 

.
\layout Enumerate

Let 
\begin_inset Formula $\mathcal{U}=\left\{ 1,2,3,\ldots,n,n+1\right\} $
\end_inset 

, let 
\begin_inset Formula $\mathcal{A}=\left\{ A\subseteq\mathcal{U}\,|\, A\ne\emptyset\right\} $
\end_inset 

, and for 
\begin_inset Formula $0\le j\le n$
\end_inset 

, let 
\begin_inset Formula \[
\mathcal{A}_{j}=\left\{ A\subseteq\mathcal{U}\,|\,\textrm{the largest element in }A\textrm{ is }j+1\right\} .\]

\end_inset 

 Use these sets to establish the equality.
\layout Enumerate

Prove the equality by induction on 
\begin_inset Formula $n$
\end_inset 

.
\layout Section

Graphs
\layout Standard

A graph 
\begin_inset Formula $G$
\end_inset 

 is connected if for each pair of vertices 
\begin_inset Formula $u$
\end_inset 

 and 
\begin_inset Formula $v$
\end_inset 

 in 
\begin_inset Formula $G$
\end_inset 

, there is a 
\begin_inset Formula $uv$
\end_inset 

-walk in 
\begin_inset Formula $G$
\end_inset 

.
 Prove that 
\begin_inset Formula $G$
\end_inset 

 is connected if and only if for each 
\begin_inset Formula $S\subseteq V(G)$
\end_inset 

 with 
\begin_inset Formula $S\ne\emptyset$
\end_inset 

 and 
\begin_inset Formula $S\ne V(G)$
\end_inset 

, there is an edge in 
\begin_inset Formula $G$
\end_inset 

 with one endpoint inside 
\begin_inset Formula $S$
\end_inset 

 and one endpoint outside 
\begin_inset Formula $S$
\end_inset 

.
\layout Section

A Proof with an Error
\layout Standard

The following inductive 
\begin_inset Quotes eld
\end_inset 

proof
\begin_inset Quotes erd
\end_inset 

 contains an error.
 What is the number of the first line in the proof that is incorrect? Why
 is it incorrect?
\layout Standard

Theorem: If 
\begin_inset Formula $n\ge1$
\end_inset 

 balls are placed into a box 
\begin_inset Formula $B$
\end_inset 

 and each ball is colored blue or yellow, then either all balls in 
\begin_inset Formula $B$
\end_inset 

 are blue or all balls in 
\begin_inset Formula $B$
\end_inset 

 are yellow.
\layout Standard

Proof:
\layout Enumerate

By induction on 
\begin_inset Formula $n$
\end_inset 

.
\layout Enumerate

Base case: If 
\begin_inset Formula $n=1$
\end_inset 

, then 
\begin_inset Formula $\left|B\right|=1$
\end_inset 

, so the theorem is clearly true in this case.
\layout Enumerate

Inductive Step: suppose 
\begin_inset Formula $n\ge2$
\end_inset 

.
\layout Enumerate

Let 
\begin_inset Formula $x,y\in B$
\end_inset 

 be two distinct balls in 
\begin_inset Formula $B$
\end_inset 

.
\layout Enumerate

Let 
\begin_inset Formula $B_{1}=B-\left\{ x\right\} $
\end_inset 

 and 
\begin_inset Formula $B_{2}=B-\left\{ y\right\} $
\end_inset 

.
 Note that 
\begin_inset Formula $\left|B_{1}\right|=\left|B_{2}\right|=n-1<n$
\end_inset 

.
\layout Enumerate

Therefore, the inductive hypothesis implies that all balls in 
\begin_inset Formula $B_{1}$
\end_inset 

 are blue or all balls in 
\begin_inset Formula $B_{1}$
\end_inset 

 are yellow.
\layout Enumerate

Similarly, the inductive hypothesis implies that all balls in 
\begin_inset Formula $B_{2}$
\end_inset 

 are blue or all balls in 
\begin_inset Formula $B_{2}$
\end_inset 

 are yellow.
\layout Enumerate

Note that the common color of all balls in 
\begin_inset Formula $B_{1}$
\end_inset 

 must be the same as the common color of all balls in 
\begin_inset Formula $B_{2}$
\end_inset 

.
\layout Enumerate

Because 
\begin_inset Formula $B=B_{1}\cup B_{2}$
\end_inset 

 and the common color in 
\begin_inset Formula $B_{1}$
\end_inset 

 is the same as the common color in 
\begin_inset Formula $B_{2}$
\end_inset 

, all balls in 
\begin_inset Formula $B$
\end_inset 

 are blue or all balls in 
\begin_inset Formula $B$
\end_inset 

 are yellow.
 
\layout Section

Pirates
\layout Standard

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.
 
\layout Standard

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 
\begin_inset Formula $n$
\end_inset 

 (
\begin_inset Formula $1\le n\le200$
\end_inset 

) pirates onboard.
 Finally, prove by induction on 
\begin_inset Formula $n$
\end_inset 

 that your guess is correct.)
\layout Section

Ramsey Theory
\layout Standard

In lecture 6, we present a classic proof from Ramsey theory and define 
\begin_inset Formula $R(m,n)$
\end_inset 

 for each 
\begin_inset Formula $m,n\ge1$
\end_inset 

.
 Describe how the proof can be modified to show that 
\begin_inset Formula $R(m,n)\le\binom{m+n}{m}$
\end_inset 

.
 (Note: you are not asked to repeat the proof in full, just describe how
 to modify the proof we saw in lecture 6.) 
\the_end