\problemdata
{induction}
{CIA}
{cube}

\begin{problem}
% strengthen inductive hypothesis
% source:  fall96

The C.I.A. wants you to design plans to build, for an arbitrary $k
\geq 1$, a $2^k \times 2^k \times 2^k$ cubic foot granite cube that is
solid except for a missing single cubic foot that is one of the eight
cubic feet nearest the center of the cube.  It will have one of its
corners exactly at the center of the large cube.  The C.I.A. is not
telling you what is to be placed inside the cube.

You are to build this by cementing together {\em basic blocks} that
are 2-foot $\times$ 2-foot $\times$ 2-foot cubes, with one one-foot
cube missing from its corner~---~as shown in the diagram below.

\begin{figure}[h]
\centerline{\psfig{figure=figures/cube.ps,height=1in}}
\end{figure}

Describe your method for doing this.  Your plans should be described
recursively on $k$.

  \solution{
    Let an $2^n \times 2^n \times 2^n$ cube with an arbitrary one-foot
    cubic block missing be denoted as an $n$-cube.  Moreover,
    throughout this problem, we assume that the one-foot block that is
    missing from any $n$-cube is at a lattice point, \ie at an
    integral number of feet from each side.

    \begin{theorem*} 
      For any positive integer $n$, any $n$-cube can be build out of
      $1$-cubes.
    \end{theorem*}
    \begin{proof} 
      Let $P(n)$ be the predicate that an $n$-cube can be build out of
      $1$-cubes.  We prove that $P(n)$ holds for any positive integer
      $n$ by induction on $n$.
      
      \begin{description}\itemsep 0ex
      \item[Base Case:~~] $P(1)$ is true since a $1$-cube is what we
        need to build.  This is precisely what we are given as a basic
        block.
 
      \item[Inductive Step:~~] We must show that for any positive
        integer $n$, $P(n)$ implies $P(n+1)$.  Consider an
        $(n+1)$-cube.  This block can be built using eight $n$-cubes
        as follows: build seven $n$-cubes such that they are all
        missing one of their corner blocks, arrange them so that their
        missing corner blocks meet in the center of the $(n+1)$-cube,
        fill up the gap with a $1$-cube such that the corner
        corresponding to the eighth $n$-cube is left empty, and,
        finally, build the eighth $n$-cube such that the appropriate
        one-foot cubic block is missing.  Notice, that the eight
        $n$-cubes can be build as desired because of the inductive
        hypothesis; that is, that any $n$-cube can be build out of
        $1$-cubes.
      \end{description}
    \end{proof}

    Now, we can state the following corollary.

    \begin{corollary*}
      For any positive integer $n$, an $n$-cube with any one-foot
      cubic block missing from its center can be build out of
      $1$-cubes.
    \end{corollary*}
    \begin{proof}
      $n$-cubes of this particular form, \ie with any one-foot cubic
      block missing from their center, is a particular case of what we
      showed in the above Theorem.  Thus, we know that $n$-cube with
      any one-foot cubic block missing from its center can be build
      out of $1$-cubes.  The construction of such a block can be done
      as outlined in the above theorem, with the exception that the
      missing one-foot block is missing from the center of the
      $(n+1)$-cube.
    \end{proof}
  }
\end{problem}
