\documentclass[11pt]{exam}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{dsfont}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol}
\usepackage{placeins}

\printanswers
%\noprintanswers

\begin{document}

\title{ EECS 203: Discrete Mathematics \\
        Group Homework 1 (Winter 2016)}
\date{Due: May 5, 2016}
\author{Answer Key}

\maketitle

\begin{questions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[10] Section 1.4 Problem 60\\
%%
\begin{solution}
\begin{enumerate}[a)]
\item $\forall x(P(x) \rightarrow Q(x))$ 
\item $\exists x(R(x) \wedge \neg Q(x))$ 
\item $\exists x(R(x) \wedge \neg P(x))$
\item Yes. The unsatisfactory excuse guaranteed by part (b) cannot be a clear explanation by part (a).
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[21] Through a bizarre set of circumstances, you find yourself on a weird game show which is a hybrid between "Who Wants to Be a Millionaire" and “Deal or No Deal”. In particular, you have a set of three cases in front of you; two are empty, and one has a million dollars inside. You're down to only one lifeline — you can phone a friend. If you were to blindly guess a case, you'd have a one-third chance of winning the million dollars, but luckily you have a friend who might be able to help. Your friend Chad is both all-knowing, and loves to play games. Chad undoubtedly knows which case holds the million dollars, but there's one problem. On any given day, Chad either always tells the truth or always lies, each with 50\% probability, and you don't know which type of day today is.

Chad’s on the line, and you can ask him two yes-or-no questions. 

\begin{enumerate}[a)]
\item Let's say you devote one question to figuring out whether today Chad is telling the truth or is lying. What is wrong with this approach to solving the problem? [2]

\item Let H denote the proposition that Chad is honest today.  Suppose you ask Chad whether some proposition p is true and he says “no.”  What can you conclude? State your answer in formal logic. [3]

\item Say you wanted to ask Chad "Chad, are you telling the truth today?"  What would Chad answer? [1]

\item Let C(n) be a predicate denoting that the million dollars is in case n (n=1 or 2 or 3). Say you ask Chad “$H\wedge C(1)$”.  How would you ask that question in English? [2]

\item Write two propositions, $P_1$ and $P_2$, that translate to two questions you can ask Chad in order to win the money.  Provide both the propositions and the English questions. [8]

\item Write a truth table starting with H and each C(n) as the inputs. For the outputs provide $P_1$ and $P_2$ as well as what Chad would answer to each of the corresponding questions.   Explain how this proves that these questions will win you the money. (Remember that the money can only be in one of the cases, so you don’t need to include rows that would have a different number of winning cases!) [5]
\end{enumerate}

%%
\begin{solution}
\begin{enumerate}[a)]
\item If we use our first question to find out whether Chad is honest today, there are only 2 ways Chad can answer our second question, while there are 3 cases to choose between.  There is at least 1 case we will never open, so if the money is there, we lost it.

\item If Chad is honest, p is false, while if he is dishonest, p is true.  This can be written in several ways: $$H\oplus p\equiv (H\wedge \neg p)\vee (\neg H\wedge p)\equiv (H\vee p)\wedge(\neg H\vee\neg p)\equiv (H\rightarrow \neg p)\wedge(\neg H\rightarrow p)$$

\item If he is telling the truth today, he will honestly say "yes", while if he is not, he will lie and say "yes".  Either way, we learn nothing.

\item "Chad, is it the case that you are honest and the money is in case 1?"

\item There are many answers to this, most if not all of which are either the same as the answers to part b (but with C(n) instead of p) or the negation of them.  My favorite is $H\leftrightarrow C(1)$ and $H\leftrightarrow C(2)$.  You can ask these questions as "Is it the case that whether you are honest is the same as whether the money is in case 1?" and "Is it the case that whether you are honest is the same as whether the money is in case 2?".  These could be restated as "If I were to ask you if the money is in case 1, would you say yes?" and "If I were to ask you if the money is in case 2, would you say yes?"

\item \ \\
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$H$ & $C(1)$ & $C(2)$ & $C(3)$ & $H\leftrightarrow C(1)$ & $H\leftrightarrow C(2)$ & Chad Says 1 & Chad says 2 \\\hline
T & T & F & F & T & F & Yes & No  \\\hline
T & F & T & F & F & T & No  & Yes \\\hline
T & F & F & T & F & F & No  & No  \\\hline
F & T & F & F & F & T & Yes & No  \\\hline
F & F & T & F & T & F & No  & Yes \\\hline
F & F & F & T & T & T & No  & No  \\\hline
\end{tabular}

If chad responds with (Yes, No), whether he is honest or not, the money is in case 1.  If he responds (No, Yes), it is in case 2.  If he responds (No, No), it must be in case 3.  There are no cases where he says (Yes, Yes).
\end{enumerate}

\end{solution}


\end{questions}

\end{document}