\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 30 September}. Unlike previous assignments, we will no longer be forgiving of submissions that do not follow the directions. By now, everyone should know how to generate a readable PDF file and to put all of your teammate's name on the submission. }

Directions

Solve as many of the nine problems as you can. For maximum credit, your answers should be correct, clear, well-written, and convincing. The problem marked with $(\star\star)$ is challenging enough that it is not necessary to solve them well to get a ``gold-star level” grade on this assignment (although we certainly hope you will try and some will succeed!)

Cardinality of Finite Sets

1. Assume $R: A \rightarrow B$ is an total injective relation between $A$ and $B$. What must be true about the relationship between $|A|$ and $|B|$?

2. Assume $R: A \rightarrow B$ is an total surjective function between $A$ and $B$. What must be true about the relationship between $|A|$ and $|B|$?

3. Prove that for any two sets $A$ and $B$, $| A \times B | = |A| \cdot |B|$. (Recall the definition of set products from Class 8.)

Induction

1. In Problem Set 2 (Problem 6) you used the well-ordering principle to prove that any non-negative integer value less than $2^{k+1}$ can be written as $a_0 \cdot 2^0 + a_1 \cdot 2^1 + a_2 \cdot 2^2 + \cdots + a_k \cdot 2^k$ where all the $a_i$ values are either 0 or 1. Prove the same property using induction. (Hint: the induction should be on $k$.)

2. Prove by induction that every non-empty finite set of rational numbers has a minimum element. (Bonus: explain why this does not contradict the fact that the rational numbers are not well ordered.)

3. A convex polygon is a polygon where all line segments connecting any two points in the polygon are fully contained in the polygon. For example, of the three polygons below, the left two are convex, but the rightmost one is not. Prove by induction that any convex polygon with $n$ sides can be divided into $n - 2$ triangles.

\begin{center} \newdimen\R \R=0.8cm \begin{tikzpicture}[scale=1.0] \node[draw, regular polygon, regular polygon sides=5] at (0,0) {Convex}; \node[draw, regular polygon, regular polygon sides=7] at (4.5,0) {Convex}; \node[draw, star, star points=6, star point ratio=.6] at (9,0) {Concave};

\end{tikzpicture} \end{center} \begin{comment} \draw (1,0) – (0,2) – (3,3) – (4,2.5) – (2.5, -1) – cycle; \draw (1,0) – (0,2) – (2,3) – (4,2.5) – (2, 1.5) – (4, 1) – cycle; \end{comment}

Donation by Induction

(The following questions are loosely inspired by the Stata Center problem in Section 5.1.5, but any similarity to any real university is purely coincidental.)

Following the successful completion of the restoration of the Rotunda, the Board of Transients of the highly prestigious University of East Virginia, is embarking on a bold, new fund-raising initiative known as the Cornerbrick Plan. The highest priority is to tear down the monstrous Scotty Stadium to improve the view from the upper offices in Rice’s Theorem Hall. Unfortunately, it is proving harder to attract donors to fund a destruction project than it is to fund building something new that you can name.

So, a nimble board member suggests the following general process:

• The stadium is demolished, and the bricks are grouped into $n$ piles.

• For each donation, the donor gets to take one or more bricks from any one pile of their choice.

• The donor who removes the last brick gets to rename the University.

Assume there are two donors, Alice Moneybags and Bob Billionaire, who take turns making donations and taking bricks, and it is Alice’s turn first.

So, for example, if there is only one pile left (with any number of bricks), Alice can remove that pile and win (get to rename the University).

If there are two piles with one brick each, Alice has to take at least one brick. Whichever one she chooses, there is one pile left for Bob, and Bob wins.

If there are two piles left with two bricks each, Alice can either (1) remove one brick, leaving one pile with one brick, and one pile with two bricks; then Bob can remove one brick from the two-brick file, leaving things in the two piles with one brick each situation where Bob wins. Or, she could (2) remove two bricks to eliminate one pile, but this leaves the one-pile situation where it is Bob’s turn so Bob wins. Thus, whatever Alice does starting from the two piles of two bricks each situation, Bob wins.

Player 1 can win the game if there is a move she can make, such that no matter what move the other player makes, it results in a situation where Player 1 can still win the game. That is, player 1 has a winning strategy, if there is a way for player 1 to choose her moves so that no matter what player 2 does, player 1 can win.

1. Prove that if the bricks are divided into $n$ piles of a single brick each, the player who moves first wins if $n$ is odd. You should use induction for your proof (even if there may be easier ways to prove this without using induction), since setting this up as an induction proof will help you with the following questions.

2. Suppose the bricks are divided into two piles, of size $x$ and $y$. We can describe the configuration of our stadium bricks as a sequence of the number of bricks in each piles. So, the starting configuration is $(x, y)$. State clearly who should win the game dependent on $x$ and $y$, and provide a proof to support your answer. (Hint: you may find it helpful to first consider the situation where $x = y$, and prove a lemma about that.)

3. ($\star\star$) Suppose the bricks are divided into three piles, of size $x$, $y$, and $z$. State clearly who should win the game as a function of $x$, $y$, and $z$, and provide a convincing proof to support your answer. (This is rated as a $\star\star$ problem, assuming you come up with an answer on your own or with your team, without using any material from outside of this course to solve it.)