\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Week 5 Notes.}

\begin{document}
\problemset{5}                  % !! Start the problem set with its number




%%PS5 S02

\begin{problem} \textbf{Structural Induction}

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\begin{problemparts}
\problempart Prove that CW contains SMU by structural induction on the
definition of SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\problempart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\end{problemparts}
\end{problem}



%%%%%%%%
%pset2 problem7 from spring98

\begin{problem}
Define {\em constant-free one-occurrence} Boolean formulas,
{\em 1BF}'s for short,
inductively as follows:
\begin{itemize}
\item a variable is a 1BF.
\item if $F$ is a 1BF, then so is $\neg F,$
\item if $F$ and $G$ are 1BF's with no variables in common, then
%TYPO FIXED: changed \leftrightarrow to \implies:
$F \land G  \mbox{ and } F \implies G$ are 1BF's.
\end{itemize}

A {\em Boolean assignment}, $A$, is a mapping from variables to truth
values.  The {\em complement} of assignment $A$ is the assignment $B$ such
that $B(x) = \neg A(x)$ for all variables $x$ in the domain of $
A$.

Prove by induction that for all 1BF's, $F$, there is a Boolean
assignment $A$ for the variables of $F$ such that $F$ is true under
assignment $A$ and false under the complement of $A$.

\solution{
\begin{proof}
We prove the theorem by structural induction on the definition of 1BF with
induction hypothesis $P(F)$:
\[
\exists A : (F \mbox{ is true under } A) \land (F \mbox{ is false under }
\bar{A})
\]
where $A$ ranges over Boolean assignments.  Here we use the notation
$\bar{A}$ for the complement of assignment $A$.

{\em Base Case:} $F$ is a variable.  Then the desired assignment is any
$A$ such that $A(F)=\mbox{true}$.

{\em Inductive Cases:} Assume $F$ and $G$ are 1BF's with no variables in
common and that $P(F)$ and $P(G)$ hold.  We must show that $P(\neg F)$,
$P(F \land G)$ and $P(F \implies G)$.

\begin{enumerate}
\item Case $\neg F$: Since $P(F)$ holds, there is an assignment, $A_0$,
such that $F$ is true under $A_0$ and false under $\bar{A_0}$.  Then
the desired assignment $A$ for $\neg F$ will be $\bar{A_0}$.

\item Case $F \land G$: By inductive hypothesis there is an assignment
$A_0$ such that $F$ is true under $A_0$ and false under $\bar{A_0}$.
Also, there is an assignment $A_1$ such that $G$ is true under $A_1$ and
false under $\bar{A_1}$.  Now let $A$ be the assignment which agrees
with $A_0$ on the variables of $F$ and with $A_1$ on the variables of $G$.
Such an $A$ exists because no variable occurs in both $F$ and $G$.  Now
both $F$ and $G$ are true under $A$, and therefore $F\land G$ is true.
Likewise, $\bar{A}$ makes $F\land G$ false as required.

\item Case $F\rightarrow G$: As in the previous case, there are assignment
assignment $A_0$ such that $F$ is true under $A_0$ and false under
$\bar{A_0}$, and similarly for $A_1$ and $G$.  So this time we let
$A$ be the assignment which agrees with $\bar{A_0}$ on the variables
of $F$ and with $A_1$ on the variables of $G$.  Now under $A$, $F$ is
false and $G$ is true, so $F\implies G$ is true.  Likewise, $F$ is true
under $\bar{A}$ and $G$ is false, so $F\implies G$ is false under
$\bar{A}$, as required.

\end{enumerate}

\end{proof}}

\end{problem}


\begin{problem}
The
\hyperref{http://theory.lcs.mit.edu/classes/6.042/spring04/handouts/ln6.pdf}{gale}{gale}{\emph{Gale
Subset Game}} is described in
\href{http://theory.lcs.mit.edu/classes/6.042/spring04/handouts/ln6.pdf}{Course
Notes 6}.

\bparts

\ppart Prove Gale's Conjecture for the games with $m=1$ and $n=2$ or 3.

\solution{When $n=2$, $A=\set{1,2}$.  The first player can only choose a
singleton set consisting of one of the two elements.  The second player
just chooses the other one and wins.

When $n=3$, the first player can have two choices: choosing a subset
containing 1 element or 2 elements.  Whatever the first player's choice is,
the second player simply picks the complement of the first player's choice.
The game is then reduced to the case when $n=2$. Therefore, Gale's
Conjecture holds for $n=2,3$.}

\ppart Suppose the second player picks the integer $n$.  What is the
length of the shortest possible game in which no player chooses the empty
set when another move is possible?  What is the length of the longest
possible game?  Conclude that every Gale game must end.

\solution{The game will always end with a winner, because after $n > m$ is
chosen by the second player, there are only $2^n -1$ sets that are legal
picks by the players on their subsequent turns.  Therefore the game must
end after $\leq 2^n -1$ more moves.

It is possible to have this many moves in a game: the players could choose
all the subsets of size of $n-1$ first, followed by those with size of
$n-2$, and so on, down to subsets with size of 1.  Such a sequence of moves
is allowed because all the moves prior to any given move in the sequence
are subsets at least as large as the given move, so none of them is
contained in the given move.

The shortest possible game would last for $n+1$ steps. In such a game the
players always choose subsets containing one element.  When all the $n$
such sets are chosen, the only valid move is the empty set, and the game
ends.  It is not possible to end in fewer than $n+1$ moves because the $n$
subsets with size 1 can always be picked if they have not been picked
before.}

\ppart Try to prove Gale's Conjecture for $n=4$.  \hint You will be
overwhelmed with cases if you don't identify ``symmetric'' cases.  For
example, if player 1's first move is $\set{1,2,3}$, and you work out how
player 2 will win, then you can adapt your strategy to work against {\em
any} first move consisting of a set of size three, by permuting the roles
of~1, 2, 3, and~4.

\solution{There are three cases for the move of the first player
when the game starts:

\begin{enumerate}
\item The first player chooses a subset of 1 element.  The second player
then should choose the complement of the first player's choice.  The game
then becomes the same as playing the $n=3$ game on the set just chosen by
the second player.

\item The first player chooses a subset of 3 elements.  The second player
should choose the complement of the first player's choice.  The game then
becomes the same as playing the $n=3$ game on the set just chosen by the
first player.

\item The first player chooses a subset of 2 elements $C_1=\set{a,b}$.  The
second player then picks the complement of the first player's choice,
$C_2=\set{c,d}$.  We then have the following cases:
\begin{enumerate}

\item If the first player choose a subset of one element contained in
$C_1$ or $C_2$, say, $\set{a}$, the second player can choose the subset containing
only the element which remains in the same set, i.e., $\set{b}$.  The game
is then reduced to the case when $n=2$.

\item
If the first player chooses a subset of two elements --- necessarily one
element from $C_1$ and the other from $C_2$, say, $\set{a,c}$.  The second
player chooses the complement of it, $\set{b,d}$.  We have two remaining
possible subcases:
\begin{enumerate}

\item If the first player chooses one of the remaining sets of size two,
say $\set{a,d}$, player two should choose its complement, $\set{b,c}$.  The
remaining possible moves are the four sets of size 1, where the second
player clearly wins after two more rounds.

\item If the first player chooses a set of 1 element in $C_1$ or $C_2$,
say, $\set{a}$, player two should choose the set containing only the element
remaining in the set, i.e., $\set{b}$.  The game is then reduced to the case
when $n=2$.
\end{enumerate}
\end{enumerate}
\end{enumerate}
Therefore, player also has a winning strategy in the Gale game for $n=4$. 
}
\eparts

\if
\solution{

Here are a set of alternate solutions written in a slightly different format.

\begin{problemparts}
\problempart
$n=2$:

P1 cannot choose the set $\set{1,2}$ and must either choose
the empty set or a set containing one element.

Case 1: P1 chooses the empty set and loses immediately.

Case 2: 
\begin{enumerate}
\item
P1 chooses a set containing one element, without
loss of generality assume P1 chooses the set $\set{1}$. 

\item
In this case, P2 can choose the set $\set{2}$. 

\item 
Now P1 has no choice
but to choose the empty set and lose.
\end{enumerate}

Therefore, P2 has a winning strategy.

$n=3$:

P1 cannot choose the set $\set{1,2,3}$ so must either choose
the empty set, a set containing one element, or a set containing
two elements.

Case 1: P1 chooses the empty set and loses immediately.

Case 2: 
\begin{enumerate}
\item
P1 chooses a set containing one element, WLOG assume
P1 chooses the set $\set{1}$. 

\item
Then, P2 chooses the set $\set{2,3}$.

\item At this point, P1 can either choose the empty set
(loses immediately), or a remaining set of 1 element (all other
2 element sets contain the element $1$). If P1 chooses a 
remaining set of 1 element, P2 chooses the final 1 element
set and P1 is forced to choose the empty set next.

Thus, P2 has a winning strategy in this case.

\end{enumerate}

Case 3: 
\begin{enumerate}
\item
P1 chooses a set containing two elements. WLOG assume
P1 chooses the set $\set{1,2}$.

\item 
P2 now chooses the set $\set{3}$. 

\item
At this point, P1 is forced
to either choose a set of size 0 or a set of size 1 (all remaining
sets of size 2 contain the element $3$). If P1 chooses a set of
size 0, P1 loses immediately. If P1 chooses a set of size 1 that
remains, P2 chooses the final set of size 1 that hasn't been picked
and P1 loses as P1 has no choice but to pick the empty set.

Thus, P2 has a winning strategy for $n=3$.
\end{enumerate}

\problempart
Since no smaller set can contain any larger set, begin with the
sets of size $n-1$, picking each one, then all $n-2$ sized sets,
etc. etc. until the empty set is picked. This is exactly the size
of the power set of $\set{1,2,...,n}$ minus the original set, which
must be the maximum. The only legal moves are to pick proper subsets 
of the original set are choosen in this game without duplication, and
this sequence of moves contains all possible proper subsets. The game 
lasts: $2^n-1$ turns. 

The shortest game would result if the first player chooses the empty
set immediately, a length 1 game.

Since the longest a game can last is finite, the game must end.

\problempart

There are 4 cases. Either P1 can choose the empty set (loses 
immediately), a set of size 1, a set of size 2, or a set of size 3.

Case 1:
\begin{enumerate}
\item
P1 chooses a 1 element set, WLOG assume the set is $\set{1}$.

\item
P2 chooses the set $\set{2,3,4}$.

\item
P1 can either choose a set of size 0, 1, or 2 (0 is a loss). If
P1 chooses a set of size $1$ (WLOG say $\set{2}$), then P2 chooses 
the last set of size $2$ ($\set{3,4}$) and P1 is again 
forced to pick a set of size $1$ (WLOG say the set $\set{3}$. Then
P2 picks the remaining set of size $1$ and P1 is forced to choose
the empty set.

Thus, in this case P2 has a winning strategy.
\end{enumerate} 

Case 2:
\begin{enumerate}
\item
P1 chooses a 2 element set, WLOG assume the set is $\set{1,2}$.

\item
P2 chooses the set $\set{3,4}$

\item
P1 cannot choose a set of size 3, as every set of size 3 will
contain either $\set{1,2}$ or $\set{3,4}$ by something called the
pigeon hole principle we'll learn later. Thus, P1 has to
choose a set of size 0, 1, or 2. Again, P1 choosing a set of
size 0 leads to an immediate loss. 

If P1 chooses a set of size
$1$ (WLOG assume the set is $\set{1}$ because all 1 element sets
are equivalent in that a single 2 element set already chosen
has the element in it). Then P2 chooses the single element 
set such that no more size $2$ sized sets can be chosen (in
this case the set is $\set{2}$). Then P1 is forced to choose
another set of size 1, and P2 chooses the last set of size 1 
and P1 has to choose the empty set.

If P1 chooses a set of size $2$ (WLOG assume the set is $\set{1,3}$),
then P2 chooses another set of size 2 that can be legally
picked ($\set{1,4}$). P1 can again choose a set of size 1 at this
point, or another set of size 2. If P1 chooses a set of size 1,
P2 proceeds as above and wins. Thus, P1 must choose another
set of size 2. Note that there are a total of 6 size 2 sets,
thus P1 will be forced to stop picking size 2 sets first. At
that point, P1 picks a set of size 1 (say $\set{1}$), then P2 picks
the element $\set{2}$ and, P1 is forced to pick the 2nd to last 
1 element set, and P2 finishes by picking the last 1 element
set. Then P1 is forced to pick the empty set.
\end{enumerate}

Case 3:
\begin{enumerate}
\item
P1 chooses a 3 element set, WLOG say $\set{1,2,3}$.

\item
P2 chooses the 1 element set $\set{4}$.

\item
There are no more 3 element sets remaining that do not contain $4$,
so P1 must choose a set of size 1 or 2. 

If P1 chooses a set of size
1 (say $\set{1}$), P2 chooses the last set of size $2$ ($\set{2,3}$). Then
P1 must chose another set of size 1, and P2 picks the last set of
size 1. Finally, P1 is forced to pick the empty set again.

If P1 chooses a set of size 2 (WLOG, say $\set{1,2}$), then P2 chooses
the 1 element set that means no more 2 element sets can be picked
(in this case $\set{3}$). Then P1 must choose a 1 element set, and P2
picks the final 1 element set, forcing P1 to pick the empty set
in the end.

Thus, P2 has a winning strategy for $n=4$.
\end{enumerate}
\end{problemparts}
}
\fi

\end{problem}

\end{document}


