Problem 0: Review old problem sets, practice problems, and exams. If you find a topic that is missing from these examples, suggest a corresponding practice problem on Ed.

Problem : Write negations of the following sentences.

Problem : Let $L(x, y)$ be the predicate "$x$ lives in $y$". Let $S(x, y)$ be the predicate "$x$ shops at $y$". Let the domains of the variables and the truth of the predicates for particular values be as indicated by the tables given below. Use $P$ for the set of people, $C$ for the set of cities (ignoring the fact that Columbia and Timonium are Census Designated Places, not cities), and $S$ for the set of stores.

 $L$$S$
 ClintonBranfordTrumbullAldiWegmansShoprite
Chidi✓  ✓ ✓
Eleanor✓  ✓✓
Tahani✓  ✓ ✓
Jason  ✓  ✓
Janet ✓ ✓  

Write each of the following English statements symbolically and determine whether they are true or false. Explain your answers briefly.

Problem : Prove or disprove: for any integers $a$, $b$, $c$, and $d$, if $a + b \mid d$ and $a + c \mid d$ then $b + c \mid d$.

Problem : Find an integer $r$ such that $0 \le r \le 12$ and $11^8 \equiv r \pmod{13}$.

Problem : Find the smallest $k$ such that any amount of at least $k$ cents can be made with 4-cent and 5-cent stamps. Prove your answer.

Problem : Define a sequence by $d_1=3$ and $d_k = 6 \cdot d_{n-1} + 2$ for $n \ge 2$. Find an explicit formula for $d_n$.

Problem : Define a sequence by $c_0 = 8$, $c_1 = 21$ and $c_k = 5 \cdot c_{k-1} - 6 \cdot c_{k-2}$ for $k \ge 2$. Find an explicit formula for $c_n$.

Problem : Prove that for any sets $A$ and $B$, $A \cup (A \cap B) = A$ using no properties of sets other than the definitions of the set operations.

Problem : Prove that, for any sets $A$, $B$, $C$, and $D$, if $C \subseteq A-B$ and $D \subseteq B-A$ then $C$ and $D$ are disjoint.

Problem : Prove or disprove: for any sets $A$ and $B$, ${\cal P}(A-B) = {\cal P}(A) - {\cal P}(B)$.

Problem : A state issues license plates in two formats: either two letters followed by three numbers, or 5 numbers with a letter somewhere between them (but not at the ends). How many different license plates can the state issue?

Problem : Imagine a game like poker but played with 4 card hands. Which should be a better hand: one pair or ``melting pot'', which is four cards all of different ranks and different suits (that is, which is less likely to be made from a randomly dealt hand of 4 cards)?

Problem : 50 people were surveyed about what TV shows they watch. 21 reported that they watch The Amazing Race, 25 watch Veronica Mars, and 11 watch Arrested Development. 3 watch AD and TAR, 9 watch TAR and VM, 3 watch VM and AD, and 1 watches all 3. Fill in the Venn diagram that shows how many people watch each possible combination of shows. (And guess the year.)

Problem : 12 people are to be seated for a jury. The jury pool consists of 20 people: 7 college students, 10 retirees, and 3 working professionals.

Problem : The game Can't Stop is played with 4 indistinguishable 6-sided dice. How many distinct outcomes are there of rolling the dice?

Problem : Define $f: {\bf R} \rightarrow {\bf R}$ by $f(x) = (x - 1)(x + 2)(x + 3)$. Is $f$ 1-1? Is $f$ onto? Explain your answers.

Problem : Define $f:\{0,1\}^* \rightarrow {\bf Z}$ by $f(s) = $the length of the longest sequence of 0's in $s$ (so, for example, $f(00000) = 5$, $f(11001) = 2$ and $f(111) = 0$). Is $f$ 1-1? Is $f$ onto? Explain your answers.

Problem : Is the set of nondecreasing functions from $\mathbb{N}$ to $\{0, 1, \ldots, 99\}$ countable or uncountable? Justify your answer.

Problem : Is the set of nondecreasing functions from $\mathbb{N}$ to $\mathbb{N}$ countable or uncountable? Justify your answer.

Problem : Consider the relation $R$ on ${\bf Z^+}$ defined by $xRy$ if and only if $gcd(x,y) \gt 1$.

Problem : Consider the relation $S$ defined on finite-length strings of letters a,...,z defined by $xSy$ if and only if $x$ is a substring of $y$ (in Java terms, if there are integers a and b so that y.substring(a,b).equals(x)).

Problem : Consider the relation $T$ defined on ${\bf Z}_{10} = \{0,1,2,3,4,5,6,7,8,9\}$ defined by $xTy$ if and only if $3|(x^3-y^3)$. Show that $T$ is an equivalence relation and give the corresponding equivalence classes.

Problem : Let $\preccurlyeq$ be a partial order on a set $S$. Let $R$ be the relation defined by $xRx$ for all $x \in S$ and $xRy$ when $y \preccurlyeq x$ and $x \ne y$. What can you say about $R$?

Problem : Let $G$ be a directed graph and define a relation $R$ on the vertices of $G$ by $uRv$ if and only if either $u=v$ or there is a path on which $u$ precedes $v$. Under what conditions is $R$ a partial order?

Problem : Use the definition of $\Theta$ to show that $3n^3-4n^2+10n-5$ is $\Theta(n^3)$.

Problem : Order the following functions so that if $f$ comes before $g$, then $f$ is of order at most $g$ ($f(n)$ is $O(g(n))$). Indicate which functions can be switched in the lists (in other words, indicate which are of the same order as each other).