%\input{params}
\documentclass[11pt,twoside]{article}
    
\usepackage{graphics}
\newcommand{\nand}{|}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\printlayout
\askaboutsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut8}
\newcommand{\tutnum}{8}
\newcommand{\tutdate}{October 27, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}


\problem

\textbf{Life and Death.}
In ancient Mars, cannibalism was an essential way of life. 
The Marons and the Batons
were two species that lived for several thousand years in 
close contact.
Every year, first all the Marons sustained themselves by first
consuming Batons: two Marons ate one Baton between them.
Then they reproduced: one-year-old Marons 
doubled in number
while Marons that were two or older tripled in number.
Then the surviving Batons consumed one Maron each
and then all the Batons reproduced to quadruple in number. This cycle
repeated every year. After 1 year there were two 1-year old Marons and
two 1-year old Batons. After 2 years there were two 1-year olds and
two 2-year olds in each of the two species.  How many of each 
will there be of each species at the end of $n$ years?

\textbf{Solution}:
Let $g(n)$ be the number of Marons after $n$ years, and $f(n)$ the number
of Batons.

After $n-1$ years, we have $g(n-1)$ Marons and $f(n-1)$ Batons.
Then in the $n^{th}$ year, 
from the rules of sustenance, the population of Batons
drops to $f(n-1) - (1/2)g(n-1)$. The number of 1-year old
Marons is $g(n-1) - g(n-2)$. Their population goes up to 
$2(g(n-1) -g(n-2))$. Meanwhile the number of older Marons goes
up from $g(n-2)$ to $3g(n-2)$. 
Then it is the Batons turn. The survivors consume a Maron each. 
So the population of Marons after $n$ years is
$$g(n) = 2(g(n-1)-g(n-2)) + 3g(n-2) -(f(n-1)-\frac{1}{2}g(n-1))$$
That is, $$g(n) = \frac{5}{2}g(n-1) + g(n-2) - f(n-1)$$

The Batons then quadruple.
So the number of Batons after $n$ years is:
$$f(n) = 4(f(n-1) - \frac{1}{2}g(n-1))$$

We know that $f(1) = g(1) = 2$ and $f(2) = g(2) = 4$.
Substituting these values in the recurrences, we get 
$f(3) = g(3) = 8$ and $f(4) = g(4) = 16$.

We guess that $g(n) = f(n) = 2^n$.
We can verify this by strong {\em double} induction. Note that there
is only 1 variable, $n$, the number of years, but we will argue
inductively about both $f(n)$ and $g(n)$. 

I.H. : $P(n): f(n) = g(n) = 2^n$.

Base:  $n=1$:  $f(1) = g(1) = 2$ and 

      $n=2$: $f(2) = g(2) = 4$. 

Ind. Step.:  Assume $P(k)$ is true for  $1 \leq n$.
To prove $P(n+1)$ consider $f(n+1), g(n+1)$.
$$f(n+1) = 4(f(n) - \frac{1}{2}g(n)) = 4(2^n - 2^{n-1})$$
$$ = 4(2^{n-1}) = 2^{n+1}$$
And,
$$g(n+1) = \frac{5}{2}g(n)+g(n-1) -f(n) = \frac{5}{2}(2^{n}) + 2^{n-1} - 2^n
= 2^{n+1}$$


\problem

{\textbf Stepping up. } Alice the ``elegant'' climbs up a flight
of stairs one or two stairs in one stride. Bob the ``elongated beast'' on the
other hand clambers up 2, 4, 6 or any even number of stairs in one stride. 
Who can climb a flight of $n$ stairs in more ways? (Assume $n$ is even. 
A {\em way} of climbing a flight of $n$ stairs is the sequence of strides
taken to get to the top. E.g. to climb up 4 stairs, Alice can go
1,1,1,1 or 1,1,2, or 1,2,1, or 2,1,1 or 2,2 i.e., in 5 different ways in all.)


\textbf{Solution}:
Let $A(n)$ be the number of ways Alice can climb up a flight of $n$ stairs.
Then, using the fact that her last stride is a 1-step or a 2-step,
$$A(n)= A(n-1)+A(n-2)$$ where $A(1) = 1, A(2) = 2, \ldots$. This is the
familiar Fibonacci recurrence, So $A(n) = F_{n+1}$, the $(n+1)^{th}$ Fibonacci
number. 

Similarly Let $B(n)$ be the number of ways Bob can climb $n$ stairs.
Assume $n$ is even. 
$$B(n) = B(n-2) + B(n-4) + \ldots + B(2)$$
From this we can say that for $n \geq 4$,  
$$B(n-2) = B(n-4) + \ldots + B(2)$$ 

Subtracting the latter equation from the former,
$$B(n) - B(n-2) = B(n-2)$$ 
$$B(n) = 2B(n-2)$$

We can solve this by expanding the recurrence relation repeatedly:
$$B(n) = 2B(n-2) = 4B( n-4) = 2^3B(n-6) = 2^kB(n-2k) = 2^{n/2 -1}B(2)$$
$$B(n) = 2^{n/2 -1}$$

But then $B(n) \leq F_{n+1} = A(n)$.



\problem

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


We use the pigeonhole principle.
Let the pigeons be the elements $s \in S$, and 
the holes be the numbers $0 \ldots 1996$.  Let $s$ be placed in 
$s \bmod 1997$.

Since there are more than 1997 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 1997 = r = s_i \bmod 1997$, 
$s_j - s_i \bmod 1997 = 0$, so $1997 \mid (s_j - s_i)$.  But 
$gcd(1997,10^i) = 1$, so 1997 must divide $s_{j-i}$.

%%%%%%%%%%%%%%%
%\problem
%
%Show that in any sequence of $n$ integers, there is either an 
%increasing subsequence of length $\sqrt{n}$ or a decreasing subsequence
%of length $\sqrt{n}$. 
% \begin{enumerate} 
%  \item Show that every DAG has a chain of length $> \sqrt{n}$ or an antichain of size $\geq \sqrt{n}$.
%  \item Define a DAG based on a given sequence of numbers so that chains
%correspond to increasing subsequences and antichains correspond to decreasing
%subsequences.
%  \item Put the above together to solve the problem.
%  \end{enumerate}

%
%\begin{enumerate}
%\item From Dilworth's theorem for every $t > 0$, there is either a chain
%of length $> t$ or an antichain of size $\geq \lceil n/t \rceil$.  For $t = \sqrt{n}$,
%this is exactly the statement we want to prove.
%
%\item We define a DAG whose vertices are the numbers in the sequence. For the
%ordering, define $(a, b)$ to be an edge if either $a = b$, or else
%$(a < b$ and $a$ comes before $b$ in the sequence).  A chain corresponds
%to an increasing subsequence moving to the right, but what does an antichain
%correspond to?
%
%\begin{lemma}
%If $a,~b$ are incomparable and $a > b$ then $a$ precedes $b$ in the sequence.
%\end{lemma}
%\begin{proof}
%By contradiction.  Assume $b$ precedes $a$.  Then $b < a$ and $b$ precedes
%$a$, so $(b, a)$ is an edge.  This contradicts our assumption that $a$ and
%$b$ are incomparable.
%\end{proof}
%
%Extend this to more than 2 elements:
%
%\begin{lemma}
%If $a_1,~a_2,~\ldots,~a_t$ are incomparable and $a_1 > a_2 > \cdots a_t$,
%then $a_1~a_2,~\cdots,~a_t$ form a decreasing subsequence.
%\end{lemma}
%\begin{proof}
%($\forall i$), the fact that $a_i > a_{i+1}$ implies that $a_i$ precedes
%$a_{i+1}$ in the sequence, by the previous lemma.
%\end{proof}
%
%So given an antichain (a set of incomparable elements), arrange the elements
%so that they are in decreasing order and the ``left of'' relation
%follows, giving a decreasing subsequence.
%
%\item Since we have a DAG on $n$ elements, this implies that there is either
%a chain of size $> \sqrt{n}$ or an antichain of size $\geq \sqrt{n}$. By the
%analysis just above, this yields either an increasing sequence of
%length $> \sqrt{n}$, or a decreasing subsequence of length $\geq \sqrt{n}$.
%
%
%\end{enumerate}
%%%%%%%%%%%

\end{problems}

\end{document}











