\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}
\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}


%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
\handout{tut8}{Mini-Quiz 8}{April 6, 2001}
\begin{enumerate}
\item Your name:
\item In how many ways can a set of five letters be selected from the English alphabet?
\end{enumerate}
\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
\handout{tut8}{Tutorial 8 Problems}{April 6, 2001}
\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?
Investigate the asymptotic behavior of your answer.

\solution{

\textbf{Solution:}\\


$\displaystyle \frac{(2n)!}{n! 2^n} = 
\sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1))$

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, \ldots, 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}$.
Using Stirling's formula on this expression gives
\begin{displaymath}
  \frac{(2n)!}{n! 2^n}
  = 
  \frac{(2n)^{2n} e^{-2n}\sqrt{4\pi n} (1 + o(1))}
  {n^n e^{-n}\sqrt{2\pi n} (1 + o(1)) 2^{n}}
  =
  \sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1)).
\end{displaymath}


}



%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 \ . \]

}


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


% Introduction to Combinatorial Mathematics, Page 8, Example 1-11
\problem Eleven scientists are working on a secret project.  They wish to lock up the documents in a cabinet such that the cabinet can be opened if and only if six or more of the scientists are present.

\ppart What is the smallest number of locks needed?

\solution{
We must have a group of six or more scientists present to open the safe.  Therefore, for any group of five scientists, there must be at least one lock they cannot open.  Moreover, for any two groups of five scientists, there must be two different locks they cannot open, because if both groups cannot open the same lock, there is a group of six scientists among these two groups who will not be able to open the cabinet.  Thus at least $\binom{11}{5}=462$ locks are needed.
}

\ppart What is the smallest number of keys to the locks each scientist must carry?

\solution{
Let A be one of the scientists.  Whenever A is associated with a group of five other scientists, A should have the key to the lock(s) that these five scientists were not able to open.  Thus, A carries at least $\binom{10}{5}=252$.  (Although we have only shown that these are lower bounds on the numbers of locks and keys, a scheme can actually be designed using these many locks and with each scientist carrying that many keys.)
}


\problem Recall that $F_n$ denotes the $n$th Fibonacci number.

\bparts

\ppart Which Fibonacci numbers are even?  Prove it!

\solution{
Every third one is even, starting from $F_0 = 0$.  Prove this by proving
that $F_n$ is even iff $3 \mid n$ by strong induction on $n$.  The base
cases are that $F_0$ is even and $F_1$ is odd.  Now consider
\[
F_{n+1} \eqdef F_n + F_{n-1}.
\]
There are three cases, depending on what $n$ is congruent to modulo 3.

\emph{Case 0}: $n \equiv 0 \pmod 3$.  Then $n+1 \equiv 1 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n - 1 \not\equiv 0
\pmod 3$, so by hypothesis, $F_n$ is even and $F_{n-1}$ is odd, so $F_{n+1}$
is odd as required.

\emph{Case 1}: $n \equiv 1 \pmod 3$.  Then $n+1 \equiv 2 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n-1 \equiv 0 \pmod
3$, so by hypothesis, $F_n$ is odd and $F_{n-1}$ is even, so $F_{n+1}$ is
odd as required.

\emph{Case 2}: $n \equiv 2 \pmod 3$.  Then $n+1 \equiv 0 \pmod 3$.  So we
must prove that $F_{n+1}$ is even.  Now $n-1 \equiv 1 \pmod 3$, so by
hypothesis, $F_n$ is odd and $F_{n-1}$ is odd, so $F_{n+1}$ is even as
required.

}

\ppart The previous result is a special case for $m=3$ of the assertion
that $F_m \mid F_n$ iff $m \mid n$ for all $m,n \in \naturals, m > 0$.
Assuming this assertion for the time being, how many Fibonacci numbers
up to $F_{100}$ are \emph{not} multiples of 3 or 8 or 13?

\solution{

Every 4th number is multiple of $F_4 = 3$, every 6th number is multiple of
$F_6 =8$, and every 7th number is multiple of $F_7 = 13$.

Now, total = 100 (starting with $F_1$ and going to $F_{100}$)\\
mult of 3 = $\floor{100/4} = 25$,\\
mult of 8 = $\floor{100/6}= 16$,\\
mult of 13 = $\floor{100/7}=14$,\\
mult of 3 and 8 = $\floor{100/12}=8$, (since 12 is $\lcm(4,6)$),\\
mult of 3 and 13 = $\floor{100/28}=3$ (since 28 is $\lcm(4,7)$),\\
mult of 8 and 13 = $\floor{101/42}=2$, (since 42 is $\lcm(6,7)$),\\
mult of 3 and 8 and 13 = $\floor{101/84}=1$, (since 84 is $\lcm(4,6,7)$).

So the answer is $100 - 25 - 16 - 14 + 8 + 3 + 2 - 1 = 57$.
}

\eparts


\end{problems}
\end{document}

















