\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parindent0pt

\begin{document}

\tutorial{tutorial3}{Problems for Tutorial 3}{February 24, 1997}

\section{Graphs.....}

An n-cube, $Q_n$, is a graph with vertices and edges that can be 
created in the following way:

$Q_0$ is one vertex.

$Q_n$, for $n \ge 1$ is formed by taking an ($n-1$)-cube, $Q_{n-1}$, making
a copy of it, and connecting each pair of corresponding nodes.

\begin{picture}(500, 150)(-50, 20)

\put(10,50){\circle*{4}}

\put(10,25){$Q_0$}

\put(50,50){\circle*{4}}
\put(50,100){\circle*{4}}
\put(50,50){\vector(0,50){48}}
\put(50,25){$Q_1$}

\put(100,50){\vector(1,0){48}}
\put(100,100){\vector(1,0){48}}
\put(100,50){\circle*{4}}
\put(100,100){\circle*{4}}
\put(100,50){\line(0,50){50}}
\put(150,50){\circle*{4}}
\put(150,100){\circle*{4}}
\put(150,50){\line(0,50){50}}
\put(125,25){$Q_2$}


\put(200,50){\vector(1,1){23}}
\put(200,100){\vector(1,1){23}}
\put(250,50){\vector(1,1){23}}
\put(250,100){\vector(1,1){23}}


\put(200,50){\line(1,0){48}}
\put(200,100){\line(1,0){48}}
\put(200,50){\circle*{4}}
\put(200,100){\circle*{4}}
\put(200,50){\line(0,50){50}}
\put(250,50){\circle*{4}}
\put(250,100){\circle*{4}}
\put(250,50){\line(0,50){50}}

\put(225,75){\line(1,0){48}}
\put(225,125){\line(1,0){48}}
\put(225,75){\circle*{4}}
\put(225,125){\circle*{4}}
\put(225,75){\line(0,50){50}}
\put(275,75){\circle*{4}}
\put(275,125){\circle*{4}}
\put(275,75){\line(0,50){50}}
\put(220,25){$Q_3$}

\end{picture}

A set of vertices in a graph is called {\em independent } if no 
two vertices in the set are adjacent.  The {\em independence number}
of a graph is the maximum number of vertices in an independent set of 
vertices for the graph.

a) Show that the number of vertices in $Q_n$ is $2^n$.

b) Show that $2^{n-1}$ is an upper bound for the independence number of $Q_n$.

c) Prove that $Q_n$ has an independent set of size $2^{n-1}$ .

\section{Uniqueness of Factorization}

Prove the following theorem: \\
Every positive integer can be written as a unique product of primes (where order
is irrelevant).

\section {A Number Theory Application}
 
\noindent Suppose I have a collection of switches numbered $0$ through
$n$, all initially off.  Someone comes and flips every switch (so they
are all on).  Another person then flips every second switch, starting
with $0,2,\ldots$.  The next person flips every third switch, and so
on until the last person flips only the switches numbered $0$ and $n$.
Which switches are on at the end?  Prove it.
 
 
\end{document}
