\problemdata
{strong induction}
{S00 ps2}

\begin{problem}
% multi base cases, strong induction

One plan considered by the 6.042 staff, then dropped, involved
requiring students in tutorials to work in groups of either exactly 4
or exactly 7 students. 
We abandoned this plan when we realized that a tutorial section of
size 13 could not be split up in this way.

\begin{problemparts }

\problempart What is the smallest number $k$ such that all tutorials of $k$
or more students \emph{can} be split into teams of 4 and 7?
\solution{
The smallest number $k$ such that all tutorials of $k$ or
  more students \emph{can} be split into teams of 4 and 7 is $18$.
}

\problempart Prove that $k$ is the smallest such number.
\solution{
 A tutorial of size $17$ \emph{can not} be split into teams of
  4 and 7.  In particular, a tutorial of size $17$ can contain at most
  2 groups of 7.  Consider the various possible splits of the
  tutorial: i) no groups of 7: since the only other group size is 4 we
  can not split the tutorial of 17; ii) one group of 7: the remaining
  10 students can not be split into groups of 4; iii) two groups of 7:
  the remaining 3 students can not be split into groups of 7.
}


\problempart Prove (by induction) that all tutorials of $k$ or more students
can be split into teams of size 4 and 7.
\solution{
The proof is by strong induction on the size $n$ of the
  tutorial.  Let $P(n)$ be the predicate that a tutorial of size $n$
  can be split into groups of size 4 and 7.

  We must show that $P(n)$ holds for all $n \geq 18$.

  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=\kill
    1. \textbf{Base Case:} $P(18)$, 18 = 4 + 7 + 7 \\
    2. \textbf{Base Case:} $P(19)$, 19 = 4 + 4 + 4 + 7 \\
    3. \textbf{Base Case:} $P(20)$, 20 = 4 + 4 + 4 + 4 + 4 \\
    4. \textbf{Base Case:} $P(21)$, 21 = 7 + 7 + 7 \\
    5. \textbf{Inductive Step:} 
    $\forall\; n \geq 21, ( \forall\; k \in [18,n], P(k) ) \implies P(n+1)$ \\
    \> 1. Fix $n \geq 21$.\\
    \> 2. From the inductive hypothesis $P(k)$ holds, for all $k \in [18,n]$. \\
    \> 3. In particular, $P(n-3)$ holds. \\
    \> 4. The size of the $n+1$ student tutorial is $4$ students
    greater than the $n-3$ student tutorial. \\
    \> 5. Thus, we can split up the $n+1$ tutorial as the $n-3$ tutorial \\
    \> \quad\ and with an extra 4 student group. \\
    \> 6. QED \\
    6. QED                        
  \end{tabbing}
}


\end{problemparts}
\end{problem}
 


