\documentclass[11pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}

\def\BOX#1{\fbox{\vbox to #1{\vss\hbox to #1{\hss}}}}
\def\Bigbox{\BOX{0.25in}}
\def\Bigbox{\raisebox{-0.5ex}[0.25in][0pt]{\BOX{0.25in}}}

% =========================================================
\begin{document}

\begin{center}
\LARGE \textbf{CS 173: Discrete Mathematical Structures, Fall
2009}
\\
\textbf{Honors Homework 2}
\\[1ex]
\Large Due by 5pm on 
Wednesday 14 October.
Please give to Margaret 
or push it under the door of Margaret's office (3214 Siebel).

Your homework must be formatted using latex.   Please turn in
hardcopy (latex output only, don't worry about the source).

\end{center}

A binary operation on a set $A$ is a function that takes two
elements of $A$ and returns an element of $A$.   For example,
addition and multiplication are binary operations on the set of
real numbers.   

Suppose that $\ast$ is a binary operation on a set $A$.
Then $\ast$ is {\it commutative} if 

$$\forall x,y \in A, x \ast y = y \ast x$$

and $\ast$ is {\it associative} if

$$\forall x,y,z \in A, x \ast (y \ast z) = (x \ast y) \ast z$$

For example, multiplication of real numbers is commutative and
associative, but subtraction is neither.  E.g. $(3 - 2) -1 = 0
\not = 2   = (3 - (2 -1)$.
However, the two
properties are actually independent of one another.

\begin{enumerate}
%----------------------------------------------------------------------
\item 
Show that exponentiation (i.e. $x^y$) is neither commutative
nor associative.   Show that both properties fail using concrete counter-examples.


%----------------------------------------------------------------------
\item 
Let's define the operation $\bigtriangleup$ on the real numbers as follows:

$$x \bigtriangleup y = \frac{2xy}{x+y}$$

\noindent
This is often called the ``harmonic mean''.
Is $\bigtriangleup$ commutative?  associative?  Prove that your answers are
correct.  (Use a general argument if it's true, a concrete counter-example if
it's false.)



%----------------------------------------------------------------------
\item 
Suppose that we have a three-letter sequence such as $ABC$.
A permutation is a way to reorder the sequence.   For example, one
permutation $k$ swaps the first and last characters.   So $k(ABC) = CBA$
and $k(BCA) = ACB$.
Another permutation (call it $p$) rotates the letters rightwards.   So
$p(ABC) = CAB$ and $p(CBA) = ACB$.  Or, we can define a third permutation
$m$ which swaps the first two letters in the sequence, i.e.
$m(ABC) = BAC$ and $m(CBA) = BCA$.

We can ``multiply'' two permutations by doing one after another.   So
$kp(ABC) = k(CAB) = BAC = m(ABC)$.  So $kp = m$.   (Notice the rightmost
permutation in the product is applied first, so the order is 
like function composition.)

\begin{enumerate}
\item For a fixed input sequence of three letters, there are six possible outputs
and thus six possible permutations.   We've seen three above.   Write down
the other three.  If you have trouble finding all three missing ones, it may help
to start trying to build the table in part (b) and see if it suggests what might
be missing.

\item Write out a multiplication table for the set of six permutations.   That is,
for each pair of input permutations, show which output permutation you get
when you multiply them together.    

\item Use a concrete counter-example to show that this multiplication operation is
not commutative.

\end{enumerate}
\end{enumerate}


\end{document}
