\problemdata      
        {?} % latex-friendly label for the prob.
        {Logic, Graphs, Probability-Intro} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, final} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
Suppose we construct a simple undirected graph $G$ with vertex set
$V=\set{1,2,\dots,n}$, as follows:
\begin{itemize}
\item
First, we color the nodes: For each $x\in V$, we flip a coin twice. 
If we get heads in both tosses, we paint $x$ blue; otherwise, we paint 
$x$ red. 
\item
Next, we draw the edges: For each unordered pair $\set{x,y}$ of
distinct vertices from $V$, we roll a die. If we get~$6$, we draw
the edge connecting $x$ and $y$; otherwise, $x$ and $y$ remain
unconnected.  
\end{itemize} 
The coin and the die are both fair; every toss and every roll occurs
independently from any other toss and any other roll. 

For a vertex $x\in V$, let $B(x)$ denote the property ``$x$ is blue'' and
$R(x)$ denote the property ``$x$ is red''. Similarly, for vertices $x,y\in
V$, let $E(x,y)$ denote the property ``there is an edge connecting $x$ and
$y$''. For example, the formula
\[
E(1,2) \wedge 
R(1)   \wedge 
\forall x\, x\neq 1 \implies B(x)
\]
denotes the property ``there is an edge connecting nodes $1$~and~$2$,
node~$1$ is red, and all other nodes are blue''.

Note that \emph{$E(x,x)$ is false} for every $x \in V$, because a simple
graph does not have self-loops.
\bparts

\ppart
For each one of the following properties, write down a formula that
denotes that property.  Only symbols from the list
\[
R\ B\ E\ 
=\ \neq\ 
\forall\ \exists\ 
\wedge\ \vee\ \neg\ \implies\ \iff\
x\ y\ 
(\ )\ ,\
\]
can appear in your formula.

\begin{enumerate}
\addtolength{\leftskip}{0.25in}%
\renewcommand{\labelenumi}{\roman{enumi})}
\iffalse
\item \label{item-first} ``all nodes are red'': 
\solution{
$(\forall x)R(x)$
}
\fi

\ifshowsolutions \else \vspace*{0.75in}\fi

%\item
%``all nodes are blue'': 
%
%\solution{
%$(\forall x)B(x)$
%}\hrulefill
%

%\item
%``not all nodes are blue'': 
%``at least one node is red'': 
%
%\solution{
%Any of the two: $\neg(\forall x)B(x)$, $(\exists x)R(x)$
%}

\item
``at least two nodes are red'': 

\solution{
$(\exists x)(\exists y)\bigl( x\neq y \wedge R(x) \wedge R(y) \bigr)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

\item
``the graph is complete'' (contains every possible edge)

\solution{
$\forall x\forall y\, x\neq y \implies E(x,y)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

%\item
%``the graph is \emph{not} complete'': 
%
%\solution{
%$(\exists x)(\exists y)\bigl( x\neq y \wedge \neg E(x,y) \bigr)$
%}\hrulefill

%\item
%``the graph is empty'': 
%
%\solution{
%$(\forall x)(\forall y) \neg E(x,y)$
%}

\iffalse

\item \label{item-fourth}
``the set of edges in the graph is \emph{not} empty'': 

\solution{
$\exists x\exists y\, E(x,y)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi
\fi

\item
``there exist at least two blue adjacent vertices'':

\solution{
$\exists x\exists y\, 
	E(x,y) \wedge 
	B(x) \wedge B(y)$
}
\ifshowsolutions \else \vspace*{0.75in}\fi


\item 
``every red vertex is adjacent to every blue vertex'': 

\solution{
$(\forall x)(\forall y)\bigl( 
	R(x) \wedge B(y)
	\implies
	E(x,y)
\bigr)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi


\item  \label{item-difficult}
``no two adjacent vertices have the same color'': 

\solution{
$(\forall x)(\forall y)\bigl( 
	E(x,y) 
	\implies
	\bigl( R(x) \wedge B(y) \bigr)
	\vee
	\bigl( B(x) \wedge R(y) \bigr)
\bigr)$, or

$\neg (\exists x)(\exists y)\bigl(
	E(x,y) \wedge
	R(x) \wedge B(y) 
\bigr)
$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

\end{enumerate}

\iffalse

\ppart For each one of the properties i)--iv) above, write a simple
formula in $n$ for the probability that $G$ has the property.
\begin{enumerate}
\addtolength{\leftskip}{0.25in}%
\renewcommand{\labelenumi}{\roman{enumi})}

\item	% all nodes are red
\solution{ 
	$(\tfrac{3}{4})^n$
}\brule{0.5in}
 
%\item	% all nodes are blue
%\solution{ 
%	$(\tfrac{1}{4})^n$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solution{
%	0
%}\hrulefill

%\item	% at least one node is red
%$p(n)=$\solution{ 
%	$1 - (\tfrac{1}{4})^n$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solution{
%	1
%}\hrulefill

\item	% at least 2 nodes are red
\solution{ 
	$1 - (\tfrac{1}{4})^n - n\tfrac{3}{4}(\tfrac{1}{4})^{n-1}
	=
	1 - \tfrac{3n+1}{4^n}$
}\brule{0.5in}

\item	% the graph is complete
\solution{ 
	$(\tfrac{1}{6})^{n(n-1)/2}$
}\brule{0.5in}


%\item	% the graph is not complete
%$p(n)=$\solution{ 
%	$1 - (\tfrac{1}{6})^{n(n-1)/2}$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solution{
%	1
%}\hrulefill

%\item	% the graph is empty
%$p(n)=$\solution{ 
%	$(\tfrac{5}{6})^{n(n-1)/2}$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solution{
%	0
%}\hrulefill

\item	% the graph is not empty
\solution{ 
	$1 - (\tfrac{5}{6})^{n(n-1)/2}$
}\brule{0.5in}

\end{enumerate}
\fi

\ppart For each one of the following logical formulas, write a simple
expression in $n$ for the probability that $G$ satisfies the formula.

\begin{enumerate}

\item
$\exists x\, B(x)$ \brule{0.5in}

\solution{$1 - (\tfrac{3}{4})^n$}

\item 
$\forall x\, [B(x) \vee R(x)]$ \brule{0.5in}

\solution{1}

\item 
$\forall x\, B(x) \vee \forall x\, R(x)$\brule{0.5in}

\solution{
\[
(\frac{1}{4})^n + (\frac{3}{4})^n
\]}

\item 
$\forall x\, B(x) \wedge \forall x\forall y\, \neg E(x,y)$\brule{0.5in}

\solution{
\[
\bigl(\frac{1}{4}\bigr)^n\bigl(\frac{5}{6}\bigr)^{n(n-1)/2}
\]}

\end{enumerate}


\iffalse

\ppart
What is the the probability that $G$ has
property~\eqref{item-difficult} of part~(a)? 
Your answer doesn't have  to be in closed form.

\solution{
Fix any $k\in\set{0,\dots,n}$, and any $k$ vertices $x_1,\dots,x_k\in
V$. The probability that $x_1,\dots,x_k$ are blue, the rest of the
vertices are red and there is no edge between a blue and a red vertex
is 
\begin{equation} \label{probab-1}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
\end{equation}
Since there are $\tbinom{n}{k}$ different ways to fix $x_1,\dots,x_k$,
there are exactly $\tbinom{n}{k}$ outcomes (graphs) supporting the
event that exactly $k$ vertices are blue, and there is no edge between
a blue and a red vertex, each with
probability~\eqref{probab-1}. Hence, the probability of this event is 
\begin{equation} \label{probab-2}
\tbinom{n}{k}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
\end{equation}
Finally, the event that no edge connects a blue and a red vertex is
the union of the $n+1$ disjoint events that we get by varying $k$ over 
$\set{0,\dots,n}$, each of them having probability~\eqref{probab-2}. 
Hence, the coloring is consistent with probability 
$$
\sum_{k=0}^{n}
\tbinom{n}{k}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
$$
}
\fi

\eparts
\end{problem}
