\problemdata     
{induction-4}           
{strong induction}              
{}              
{S01-PS2} 		
{S01 Karger}        	





\begin{problem} 

The 6.042 course information sheet states:

\begin{quotation}
During the second hour or so [of recitation], the students will work
in groups of three or four, and each group will be assigned a problem
to solve as a team.
\end{quotation}
\bparts
\ppart
Using strong induction, prove that if a recitation contains at least 6
students, then the class can be divided into teams, each consisting of
either 3 or 4 students.



\solution{


\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a recitation with $n$ students can be divided into teams of 3 or 4.
In the base cases, $P(6)$ is true because there could be two teams of
3, $P(7)$ is true because there could be a team of 3 and a team of 4,
and $P(8)$ is true because there could be two teams of 4.  In the
inductive step, for $n \geq 8$, assume $P(6), \ldots, P(n)$ to prove
$P(n+1)$.  If a recitation has $n+1$ students, then three students can
form a team of 3, and the remaining $n-2$ students can be divided into
teams of 3 or 4 by induction.  This shows that $P(6), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by induction.
\end{proof}
}


Another 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.


\ppart 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?

\ppart Prove that $k$ is the smallest such number.

\ppart Prove (by induction) that all tutorials of $k$ or more students
can be split into teams of size 4 and 7.



\solution{

\noindent 

\noindent
  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{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.

  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}

}
\eparts

\end{problem}
