\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{html}
\usepackage{hyperref}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\R}{{\sf R}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\ceil}[1]{\lceil #1 \rceil}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}

\begin{document}

\centerline{\bf Honors Homework 1} 

\centerline{Morally Due Mon Feb 7 at 3:30PM. Dead Cat Feb 10 at 3:30}

COURSE WEBSITE:

\url{http://www.cs.umd.edu/~gasarch/COURSES/752/S22/index.html}

(The symbol before gasarch is a tilde.)



\begin{enumerate}

\item
(0 points)
What is your name?  Write it clearly.


\item
(40 points) 
\begin{enumerate}
\item 
(10 points) 
You go to a room with 3 people $A_1,A_2,A_3$. 
1 is normal and 2 are truth tellers.
Ask YES-NO questions to them to try to determine who is who.
Try to make the number of questions as small as possible.
(Questions are sequential: Ask a question to $A_1$, and
based on the answer decide who to ask what.)

\item
(10 points) 
You go to a room with 4 people $A_1,A_2,A_3,A_4$. 
1 is normal and 3 are truth tellers.
Ask YES-NO questions to them to try to determine who is who.
Try to make the number of questions as small as possible.
(Questions are sequential: Ask a question to $A_1$, and
based on the answer decide who to ask what.)

\item
(20 points) 
You go to a room with $n$ people $A_1,\ldots,A_n$. 
1 is normal and $n-1$ are truth tellers.
Ask YES-NO questions to them to try to determine who is who.
Try to make the number of questions as small as possible.
(Questions are sequential: Ask a question to $A_1$, and
based on the answer decide who to ask what.)

\end{enumerate}

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(30 points)
For this problem we use the following definitions of $\wedge$, $\vee$, $\neg$
and are using them on variables with values in $[0,1]$. 
\begin{itemize}
\item 
$x\wedge y = xy$ (Multiplication)
\item
$x\vee y = x+y-xy$
\item
$\neg x = 1-x$. 
\end{itemize}

Let 

$$\phi(x,y,z) = (x\wedge \neg y) \vee z$$

Describe the set of all $(x,y,z)$ such that $\phi(x,y,z)$ evaluates to $\ge \frac{1}{2}$. 

\item
(30 points)
For this problem we use the following definitions of $\wedge$, $\vee$, $\neg$
and are using them on variables with values in $[0,1]$. 
\begin{itemize}
\item 
$x\wedge y = \min\{x,y\}$
\item
$x\vee y = \max{x,y}$
\item
$\neg x = 1-x$. 
\end{itemize}

Let 

$$\phi(x,y,z) = (x\wedge \neg y) \vee z$$

Describe the set of all $(x,y,z)$ such that $\phi(x,y,z)$ evaluates to $\ge \frac{1}{2}$. 

\end{enumerate}

\end{document}

