        \problemdata       % Takes 5 *mandatory* arguments
        {4-7subgroups}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 ps2-3, S00 ps2} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem} %source: spring00 ps2

% multi base cases, strong induction
One plan considered by the 6.042 staff, involved requiring students to
work in subgroups of either exactly 4 or exactly 7 students.  We abandoned
this plan when we realized that groups of 9 and 10 cannot be split up in
this way.

\begin{problemparts} 

\problempart \label{k} What is the smallest number, $k$, such that all
tutorials of $k$ or more students can be split into teams of 4 and 7?
Prove that $k-1$ students \emph{cannot} be split in this way.

\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$.

A tutorial of size $17$ \emph{cannot} 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:
\begin{enumerate}
\item no groups of 7:
the only other group size is 4.  We cannot split the tutorial of 17,
since it is not divisible by 4; 
\item one group of 7: again, the remaining
number, 10, of students is not divisible by 4; 
\item two groups of 7: the
remaining 3 students are not a group of 4 or 7.
\item three or more groups of 7: clearly, this accounts for
  $21>17$ students and is inadmissible.
\end{enumerate}
}


\problempart Now complete the proof of your answer to part~(\textbf{a}).
Namely, prove (by induction) that all tutorials of $k$ or more students
\emph{can} be split into teams of size 4 and 7.

\solution{
\begin{proof} (strong induction).  Define $P(n)$ to be the predicate that
a tutorial of size $n$ can be split into groups of size 4 and 7.  Being
``split'' really means that $n = 4x + 7y$ for some natural numbers $x,y$.
So we can give a completely precise definition:
\[
P(n) \eqdef\quad n \geq 18 \implies \exists x, y \in \naturals\ [n = 4x +
7y].
\]
We must show that $P(n)$ holds for all $n \in \naturals$.  By strong
induction, we consider $n \geq 18$ and assume the strong induction
hypothesis
\begin{equation}\label{SIH}
\forall m\ [18 \leq m < n \implies \exists x_m, y_m \in \naturals\ (m =
4x_m + 7y_m) ].
\end{equation}
in order to prove that $P(n)$ holds.

The proof divides into cases

\textbf{Case 0:} ($n < 18$) $P(n)$ holds trivially since the hypothesis $n
\geq 18$ is false.

\textbf{Case 1:} ($n=18$).  $18 = 4 \cdot 1 + 7 \cdot 2$, so $P(18)$ is
proved.

\textbf{Case 2:} ($n=19$).  $19 = 4 \cdot 3 + 7 \cdot 1$, so $P(19)$ is
proved.

\textbf{Case 3:} ($n=20$).  $20 = 4 \cdot 5 + 7 \cdot 0$, so $P(20)$ is
proved.

\textbf{Case 4:} ($n=21$).  $21 = 4 \cdot 0 + 7 \cdot 3$, so $P(21)$ is
proved.

Notice that we proved Cases 0--4, without needing to use the induction
hypothesis~(\ref{SIH}).

\textbf{Case 5:} ($n \geq 22$).  In this case, letting $m \eqdef n - 4$,
we have $18 \leq m < n$, so by induction hypothesis~(\ref{SIH}), we
conclude that there are natural numbers $x_m,y_m$ such that
\[
m = 4x_m + 7y_m.
\]
So
\begin{equation}\label{m}
n = m + 4 = 4(x_m+1) + 7y_m.
\end{equation}
Letting $x \eqdef x_m+1$ and $y \eqdef y_m$ in~(\ref{m}) implies
\[
n = 4x + 7y,
\]
which proves $P(n)$.
\end{proof}}

\end{problemparts}
\end{problem}
