\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{7W}

%% more counting, permutations, trees,..

% source: ?, fall 01 reading problem (Jaime)
% topic: counting, trees
\begin{problem} How many different possible ways could you answer next
week's reading problems if:
\begin{itemize}
\item the first problem had four true/false questions,
\item the second problem gave you one choice between four alternatives,
\item and you knew the answer to the third and last problem was an integer
 between 15 and 20 (15 and 20 included)?
\end{itemize}

\solution{384. There are 16 answers for the first part, 4 for the
 second and 6 for the third, a total of 16*4*6 = 384.}

\end{problem}


% source:  FALL 00, Pset 8, #5
% topics:  counting relations
\begin{problem}
On a set of $n$ elements how many of the following are there?

\begin{problemparts}
\problempart binary relations

\solution{$2^{n^2}$. We look at the matrix that corresponds to the relations such the element of the 
$n \times n$ matrix is 1 if the corresponding pair is in the relation and it is 0 otherwise.
 There are $2^{n^2}$ many different possible
boolean ($0-1$) $n \times n$ matrices. Another way of reasoning about
this is to say that there are $n^2$ possible ordered pairs, and any
subset of those pairs is a possible relation. If $A$ is the set of all
pairs, then all possible relations are just all possible subsets of
$A$, and we know that $P(A) = 2^{|A|} = 2^{n^2}$.}

\problempart symmetric binary relations

\solution{ In a symmetric binary relation, if (a,b) is in R, then (b,a) is in R.
The matrix associated with a symmetric relation is
symmetric (the entries in the triangle above the diagonal is the same
as the entries in the triangle below the diagonal). 
The total number of entries are $n^2$.  The number of entries on the diagonal is $n$ and the 
number of entries on the upper side of the diagonal is $(n^2-n)/2$.
Therefore there
are $\frac{n(n+1)}{2}$ entries that can be set. Hence there are
$2^{\frac{n(n+1)}{2}}$ different symmetric matrices / symmetric
relations.}

\problempart reflexive binary relations 

\solution{In a reflesive binary relations, (a,a) is in R for all a.
The matrix associated with a reflexive relation has $1$'s
along the main diagonal, so those entries are fixed. Hence the number
of entries that can be set is $n^2 - n$.  The number of matrixes is $2^{n^2 -
n}$. Therefore the number of reflexive binary relations is $2^{n^2 -
n}$. 
Note that using this idea you could count the number of relations
that are not reflexive, by just substracting the number of reflexive
relations from the total number of relations.}

\problempart symmetric and reflexive binary relations

\solution{The matrix associated with a symmetric and reflexive
relation is symmetric and has $1$'s along the main diagonal. The total number of entries
is $n^2$ and there are $\frac{n^2-n}{2}$ that are on the upper side of the diagonal.
Hence the
number of such relations is $2^{\frac{n(n-1)}{2}}$.}

\problempart symmetric or reflexive binary relations

\solution{The number of symmetric or reflexive relations $=$ the
number of reflexive relations $+$ the number of symmetric relations
$-$ the number of reflexive and symmetric relations.}

\problempart Count the number of undirected graphs with $n$ nodes,
where every node has a self-loop, by showing that there is a
one-to-one mapping (bijection) with one of the types of relations in
parts (a-e). Prove that your mapping is a bijection.

\solution{
There is a one-to-one relationship between the set of 
undirected graphs with nodes $\set{1,\dots,n}$, where every node has a
 self-loop, to the set of symmetric and reflexive binary 
relations.  To show the one to one relationship, 
we define a bijective function $f$ as follows:  for any 
undirected graph (with self loops at each node) $G$, 
$f$ maps to the symmetric and reflexive 
binary relation that contains $(a,b)$ if and only if there 
is a directed edge $(a,b)$ in $G$. 

First we show that $f$ is one-to-one.  For any two distinct undirected graphs 
(with self loops at each node) $G_1$ and $G_2$, there must exists 
an edge in $G_1$ that does not exist in $G_2$ or there must exists 
an edge in $G_2$ that does not exist in $G_1$, thus $f(G_1)$ is 
not equal to $f(G_2)$.  
Now we show that $f$ is onto.  For any symmetric reflexive relation 
$R$, there exists an undirected graph (with self loop at each node) 
$G$ such that $f(G) = R$.  This is because  
graph $G$ can always be constructed such that edge from $a$ to $b$ 
exists if and only if $(a,b)$ is in $R$.
Thus $f$ is indeed a bijection.

The number of undirected graphs with nodes $\set{1,\dots,n}$, where every node has a self-loop, is 
$2^{\frac{n(n-1)}{2}}$.
}

\end{problemparts}
\end{problem}

% SOURCE:  SPRING00, Pset 7 #9
% topic:  permutations
\begin{problem} Jack is manager of the MIT Chess Club.  After a long and
grueling match, the players have gone home, leaving Jack to put the
players' unlabeled chess sets back in their lockers.

\begin{problemparts}

\problempart If there are $n$ players/lockers and $n$ chess sets, how
many ways could Jack place chess sets in lockers such that there is
exactly one chess set in each locker, disregarding the correctness of
such placement?

\solution{$n!$. 
  Since there are $n$ chess sets and $n$ lockers, there are $n$ chess sets
  that can be place in the first locker.  $n-1$ chess sets to choose from for the second 
  locker, $n-2$ chess sets for the third... etc.  Therefore there are $n!$ possible ways.       
  }

% \problempart 
% This begs the question: how many ways can Jack achieve the feat
% of placing every chess set in the wrong locker?  Give an expression
% for general $n$ and then approximate the value for $n=10$.

% \solution{This is the number of \textit{derangements} of the set of
%   $n$ elements.  We do not know a closed form for this number, so we
%   denote it by $D_n$ as derived in Rosen, \S 5.6.  To approximate
%   $D_{10}$ we will use Stirling's approximation, $D_{10}\approx$
%   something =) }

\problempart 
Say Jack recognizes Tina's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Jack place chess sets in lockers assuming he at
least gets Tina's right?

\solution{The answer is $(n-1)!$.  After placing Tina's chess set in the 
right locker, we are left with $(n-1)$ chess sets and $(n-1)$ lockers. Thus there are
$(n-1)!$ ways to place the remaining sets. 
}

\problempart 
However Jack really resents Tina's chess prowess, and decides to get
even by putting Tina's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Tina's chess set into Tina's locker?

\solution{The answer is the total number of ways to
  place the chess sets minus the number of ways that place Tina's chess set
  correctly. This gives $n! - (n-1)!$.
}
\problempart Jack suddenly finds two more unlabelled chess sets. Now
he has $n+2$ chess sets and only $n$ lockers. He's given up worrying
about Tina now. How many ways can he place $n+2$ chess sets in $n$
lockers?

\solution{ 
The answer is $P(n+2,n)$.  There are $n+2$ chess sets to choose $n$ sets from and 
to be placed into $n$ lockers.  
$P(n+2,n)$ is the number of ways to permute $n$ objects out of $n+2$ objects which
corresponds exactly to the situation here.
}

\problempart Its been a late night, Jack gives up and goes home. Later
on Tina comes by and decides that she will put the away the $n$ chess
sets and discard the two extra checkers sets (Jack was tired). After
putting her own set into her locker
, she notices that Christos and
Ashish actually wrote their names on their sets. For reasons known
only to Tina, she decides to place the all the sets in the lockers
without regard for who they belongs to, so long as Christos's and
Ashish's sets are not in adjacent lockers (assume the lockers are
arranged in a line and tina's locker is the firstr on the line). 
How many ways can she place the chess sets?

\solution{ The
number of ways in which Christos's set and Ashish's set are next to each other can be 
counted by treating Christos-Ashish as one unit. Tina has n-1 chess sets (all minus her
own set which was put inside her locker) to start rearrange with. 
Treating Christos-Ashish as a unit she now has n-2 sets to
rearrange. The total number of rearrangements where Ashish is right before Christos is (n-2)! and 
similarly, the total number of rearrangements where Christos is right before Ashish is (n-2)!.
Adding these two numbers, the total number of rearrangements where Ashish and Christos are 
adjacent is  2.(n-2)!. 
Subtracting the total number of arrangements from that gives the number of
arrangements where Christos and Ashish are not adjacent :  (n-1)! - 2.(n-2)!.}


% \problempart 
% Jack has a sudden change of heart and decides to be nice to
% Tina.  At this time, he also realizes that Christos has
% conscientiously written his name on the outside of his chess set, so
% now Jack knows the correct destinations of two chess sets.  How many
% arrangements are there now?

% \solution{As in part (b), we can simply create an injective function
%   on the remaining elements, which gives us $(n-2)!$.}

% \problempart Say Jack is taking mind-altering drugs and has again
% changed his mind about Tina.  Still being able to discern Tina's
% and Christos's chess sets---but wishing to ill-place Tina's---Jack
% can place chess sets in lockers in how many ways?

% \solution{Assign 1 to Tina's locker and chess set, and 2 to
%   Christos's locker and chess set.  We know that $|A\cap
%   B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of functions
%   with $f(2)=2$ and $B$ to be the set of functions with $f(1)\not=1$,
%   then we know $|A|$ and $|A\cap\bar B|$, the latter of which is the
%   solution to the previous part; so, the answer is
%   $(n-1)!-(n-2)!=(n-2)(n-2)!$.  }


\end{problemparts}
\end{problem}

%------------------------------------------------
% source: tutorial 8 fall 01
% topic: Pigeon-hole
% last used: fall 01

% 

\begin{problem} 

Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $2001$.

\solution{We use the pigeonhole principle. Let the pigeons be the
elements $s \in S$, and the holes be the numbers $0 \ldots 2000$.  Let
$s$ be placed in $s \bmod 2001$.

Since there are more than 2001 elements of $S$, some hole must have
two numbers, say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.
Without loss of generality, assume that $i<j$.

Then, $s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and
$i$ 0's.  So, $s_j - s_i = s_{j-i} \cdot 10^i$.  Since $s_j \bmod 2001
= r = s_i \bmod 2001$, $s_j - s_i \bmod 2001 = 0$, so $2001 \mid (s_j
- s_i)$.  But $gcd(2001,10^i) = 1$, so 2001 must divide $s_{j-i}$.

}
\end{problem}


\iffalse
% Don't remove this yet (RAD)
% still working on it...

\begin{problem}
A possible algorithm for checking if a graph is 3-colorable is to
enumerate all possible 3 color assignments to the nodes of the graph
and then test each assignment to see if it is a valid coloring
(reminder a valid coloring is one where no two adjacent vertices have
the same color).

Let $G$ be a $n$ node graph with vertices labelled $v_1$ through
$v_n$. Let the set of colors $C=\{R,G,B\}$.

\begin{problemparts}
\problempart In how many different ways can you assign colors from $C$
to the nodes of $G$?

\solution{$3^n$}

\problempart Enumerate all the possible color assignments for a 3-node
graph with vertices $v1,v2,v3$ using the colors $C$.

\problempart There are much easier ways to check if a graph can be
colored with one color or two colors. Therefore we are really only
interested in color assignments that use {\em exactly} 3 colors. How
many such color assignments are there?

\solution{Need to substract $\leq 2$ color assignments from the total
number of $\leq 3$ color assignments from part (a). There are three
sets of two colors RG, RB, BG. For any set, the number of possible
color assignments is $2^n$. So the total number of assignments that
use exactly 3 colors is $3^n - 3.2^n$. VERIFY}

%% BETTER IDEA: easy to check 1 colors and 2 colorability therefore I
%% am actually only interested in color assignments with exactly 3
%% colors. How many color assignments are there that use exactly three
%% colors?

%% Then remove the redundant colors...but only for the three case
%% (division rule)

\noindent A valid 3-coloring of a graph is a assignment of three
colors to the nodes such that no two adjacent nodes have the same
color. One algorithm for determining whether the graph $G$ can be
colored with 3 colors is to test all possible 3 color
assignments. However several of the assignments from above are
redundant. For example, for a 4-node graph with nodes $v_1, v_2, v_3,
v_4$, the color assignment $RRRR$ is the same as the color assignment
$GGGG$ or $BBBB$. Similarly the color assignment $RGRG$ is the same as
assigning the nodes the colors $GRGR$, $BRBR$, $RBRB$, $GBBG$,
$BGGB$. By the ``same'' we mean that if one assignment is not valid,
the other ones are guaranteed to fail. In general a color assignment
is redundant, if we already checked another assignment than can be
acheived by swapping the names of the colors.


\problempart For a 3-node graph with vertices $v1,v2,v3$ , list all
possible color assignments. List only the non redundant color
assignments

\problempart (*\footnote{I do not know the solution to this
problem. It actually looks quite hard. But that's just my first
assesment, I may be wrong...} Count the number of different ways can
you assign colors from $C$ to the nodes of $G$, after removing all
redundant mappings as described above?

\solution{
Still in the works...
}

\problempart Test your answer to part (b) for a three node graph. (In
other words, list the number of non-redundant RGB colorings and see if
your answer from above yields the same number. This is a good strategy
for checking parameterized answers.)

\solution{
}
\end{problemparts}
\end{problem}
\fi

\end{document}
