\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}
\usepackage{psfig}
\usepackage{epsf}

\renewcommand{\implies}{\longrightarrow}
\askaboutsolutions

\begin{document}
\handout{tut9}{Tutorial 9 Problems}{November 3, 2000}




\begin{problems}


\problem
In lecture we demonstrated how to ``guess'' the fifth card in a poker hand
when a collaborator reveals the other four cards.  Describe a method for
guessing two hidden cards in a hand of nine cards, when your collaborator
reveals the other seven cards.

\solution{

\textbf{Solution:}\\
There must be $\ceil{9/4} = 3$ cards with the same suit, so our
collaborator chooses to hide two of them and then use the third one as
the first card to be revealed.  So this first revealed card fixes the
suit of the two hidden cards; it will also be used as the origin for
the offset position of the first hidden card.  This first hidden card
will in turn be used as the origin for the offset of the other hidden
card.  There are six cards to code the two offset positions.  These
suffice to code two offsets of size from one to six.  That is, our
collaborator can choose one of the $3! = 6$ orders in which to reveal
the first three cards and thereby tell us the offset position of the
first hidden card.  Our collaborator can then choose the order of the
final three cards to describe the offset position of the second hidden
card from the first.  Note that the first revealed card must be chosen
so that both offsets are less $\leq 6$; since the sum of the offsets
between successive cars ordered in a cycle from Ace to King is 13, it
is not possible for more than one offset between successive cards to
exceed seven, so this is always possible.
}

\problem 
In how  many ways can $2n$ students be divided into $n$ pairs?

\solution{

\textbf{Solution:}\\


$\displaystyle \frac{(2n)!}{n! 2^n}$

Consider all the ways of ordering the $2n$ students in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second students, group the third
and fourth students,..., group the $(2n-1)$th and $2n$th students. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ students can be divided into
$n$ pairs is $\frac{(2n)!}{n! 2^n}$.

}







%2. How many ways can 2n students be divided into n pairs?
% Comes from tutorial 9, spring 00.  Uses division rule.  Cute.

%3. % inclusion/exclusion


 \problem A positive integer is called {\em square-free} if it is not
  divisible by the square of any positive integer greater than 1.  For
  example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$ is
  not.  $1$ is square-free.  Use inclusion-exclusion to find the
  number of square-free positive integers strictly less than 151.
  
  \solution{
	
\textbf{Solution:}\\

We use inclusion-exclusion as done in lecture for the case
    of prime numbers. We first compute the number of positive integers
    less than 150 that are not square free.
    
    Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set
    of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
    less than 150. The cardinality of the union of these sets is given
    by
    
    \begin {eqnarray*}
      |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
      |A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
      - |A_2 \cap A_3 | - |A_2 \cap A_5|\\
      & = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
      + \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
      & &  - \lfloor 150/(2^23^2) \rfloor
      - \lfloor 150/(2^25^2 \rfloor\\
      & = & 37 + 16 + 6 + 3 + 1 -4-1\\
      & = & 58
    \end {eqnarray*}
    Therefore the number of square-free positive integers less than
    150 is
    
    \[ 150 - 58 = 92 \ . \]

}

\end{problems}
\end{document}

%The ``square-free'' problem, problem 8 from pset 7 from spring 00 DONE

%4. % Something on trees and products?
\problem
How many bit strings of length 8 have either three consecutive 0s or
four consecutive 1s?
 \solution{

\textbf{Solution:}\\

}
