\documentclass[11pt]{article}
\usepackage[Mickael]{ammaths}
\begin{document}
\en
\nocouleur
\module{How to cut a square grid ?}{3}{19}{2 periods}
\prereq{Concept of proof by induction.}
\object{\begin{itemize}
\item Conjecture a property and use induction to prove it.
\end{itemize}}
\mater{\begin{itemize}
\item Rectangular grids.
\item Scissors.
\end{itemize}}
\modpart{Problem 1 : The minimal cut length}{10 mins}
Students have to find out if there is way to minimize the length cut.
\modpart{Problem 2 : The minimal number of cuts}{45 mins}
Students have to search for a way to minimize the number of cuts, a cut being understood as a complete lengthwise and
widthwise cutting movement.
They should :
\begin{enumerate}
\item notice that the number of cuts is always the same ;
\item find the formula for the number of cuts ;
\item prove that the formula is correct, whatever the cutting method used.
\end{enumerate}
\modpart{Problem 3 : The minimal cutting time}{55 mins}
In this part, we take into account that the grid may have to be turned $90^\circ$ sometimes. If we consider that one
cut takes the same time as one turn, we can compute the time needed for each cutting plan. Students have to find a way
to minimize that cutting time, and prove the validity of their answer.
\pagebreak
\moddocdis{How to cut a square grid ?}{3}{19}{Lesson}
\begin{multicols}{2}
When preparing my lessons, I often have to cut out a square grid to make individual cards.
As it is not a particularly interesting activity, I often wonder what is \emph{the best way} to do so. The best way
could be defined as the method using :
\begin{itemize}
\itemb the minimal cut length ;
\itemb the minimal number of cuts ;
\itemb the minimal cutting time.
\end{itemize}
Consider a square grid with length $m+1$ and width $n+1$, where $m$ and $n$ are two whole
numbers.
\columnbreak
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(-1,-1)(8.5,8.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(8,5)
\psline{<->}(0,-0.5)(8,-0.5)
\psline{<->}(-0.5,0)(-0.5,5)
\uput[d](4,-0.5){$n+1$}
\uput[l](-0.5,2.5){$m+1$}
\end{pspicture}
\end{center}
\end{multicols}
\sectionblack{The minimal cut length}
This first problem is easy to solve. No matter how you do it, you'll have to cut $m$ times along the width $n+1$ and $n$
times along the length $m+1$. So the total cut length is always equal to $$m(n+1)+n(m+1)=mn+m+mn+n=2mn+m+n.$$
Therefore, there is no way to minimize the total cut length.
\sectionblack{The minimal number of cuts}
Now, there is a problem that may be worth it. If $m$ and $n$ are big enough, there are many different ways to cut out
the grid completely. Surely one of them should involve a minimal number of cuts. Of course, one could have the idea
of putting two previously cut parts one on top of the other, adjusting the lines, and cut two pieces simultaneously.
Experience shows that this is not so easy, and the cuts resulting are almost never perfect. So we will forbid this.
It's clear that for a $1\times k$ grid, $k$ cuts are needed. Now, let's study some possible ``cuting plans'' for a
$(m+1)(n+1)$ grid.
\begin{itemize}
\itemb If we first cut along the $n$ vertical lines, and then cut the $n+1$ vertical strips along the $m$ horizontal
lines, then the total number of cuts is $$n+(n+1)\times m=mn+m+n.$$
\itemb If we first cut along the $m$ horizontal lines and then cut the $m+1$ horizontal strips along the $n$ horizontal
lines, then the total number of cuts is $$m+(m+1)\times n=mn+m+n.$$
\end{itemize}
\begin{multicols}{2}
So for these two extreme situations, the number of cuts is the same. Now, let's try something a bit more complicated.
First, cut along the first vertical line from the left : $1$ cut.
\begin{center}
\psset{unit=0.4cm}
\begin{pspicture}(-0.5,-0.5)(9.5,5.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(1,5)
\psgrid[subgriddiv=0,gridlabels=0](2,0)(9,5)
\end{pspicture}
\end{center}
\end{multicols}
\begin{multicols}{2}
Then cut along the $m$ horizontal lines of the two vertical strips : $2$ times $m$ cuts.
The left-hand side strip is now completely cut out, and the right-hand side grid has been cut into $m+1$ strips. Each of
strips must be cut along its $n-1$ vertical lines.
\begin{center}
\psset{unit=0.4cm}
\begin{pspicture}(-0.5,-0.5)(9.5,9.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(1,1)
\psgrid[subgriddiv=0,gridlabels=0](0,2)(1,3)
\psgrid[subgriddiv=0,gridlabels=0](0,4)(1,5)
\psgrid[subgriddiv=0,gridlabels=0](0,6)(1,7)
\psgrid[subgriddiv=0,gridlabels=0](0,8)(1,9)
\psgrid[subgriddiv=0,gridlabels=0](2,0)(9,1)
\psgrid[subgriddiv=0,gridlabels=0](2,2)(9,3)
\psgrid[subgriddiv=0,gridlabels=0](2,4)(9,5)
\psgrid[subgriddiv=0,gridlabels=0](2,6)(9,7)
\psgrid[subgriddiv=0,gridlabels=0](2,8)(9,9)
\end{pspicture}
\end{center}
\end{multicols}
Finally, the total number of cuts is
\begin{eqnarray*}
&& 1+m+m+(m+1)(n-1)\\
&=& 1+m+m+mn-m+n-1\\
&=&mn+m+n.
\end{eqnarray*}
So the number of cuts seems to be constant, just like the cut length. It is indeed, and we will prove this result by
induction.
\bigskip
{\bf Proposition.} Any method to cut-out completely a $(m+1)\times (n+1)$ square grid involves $mn+m+n$ cuts.
\bigskip
{\sl Proof.} First, consider a $1\times (k+1)$ square grid, so $m=0$ and $n=k$. Any method to cut it will involve
$k$ cuts, and $mn+m+n=0\times k+0+k=k$ so the property is true.
Now consider any $(m+1)\times (n+1)$ square grid and assume that the property is true for any square grid
smaller than that. The first cut must be a vertical or horizontal one. Let's assume that it's vertical, the proof being
exactly the same if it is horizontal. This first cut divides the grid in two smaller grids, whose width are $k+1$, where
$k$ is a number between $0$ and $n-1$, and $n+1-(k+1)=n-k$.
According to our inductive hypothesis, any method to cut out the $(m+1)\times (k+1)$ grid will involve $mk+m+k$ cuts. In
the same way, any method to cut out the $(m+1)\times (n-k)$ grid will involve $m(n-k-1)+m+(n-k-1)$ cuts. Therefore, the
total number of cuts is equal to
\begin{eqnarray*}
&& 1+mk+m+k+m(n-k-1)+m+(n-k-1)\\
&=& 1+mk+m+k+mn-mk-m+m+n-k-1\\
&=& 1-1+mk-mk+m-m+k-k+mn+m+n\\
&=& mn+m+n.
\end{eqnarray*}
This process will ultimately end up with $1\times (k+1)$ square grids. So, by complete induction, the property is
proven. \hfill$\Box$
\sectionblack{The minimal cutting time}
Now, let's add a twist to the problem. To make a perfect cut, it's better to cut along a vertical line than along a
horizontal (where vertical is understood as the direction of the gaze of the cutter). So we can imagine that before
each cut, it's better to turn the piece in the right direction. To taje this into account, let's add 1 for each turning
of a piece of the grid, considering that this takes the same time as a cut.
In this section, all the results will therefore be given in cutting time units, a unit being the time needed to do
one complete cut or turn the piece of grid around. We consider that the cutting time is not related to the length
of the cut---which is indeed the case when using a paper cutter and not a pair of scissors.
Consider once again a $(m+1)\times (n+1)$ square grid.
If we start by cutting all the vertical lines in the current position, then we will have to rotate each of the
$n+1$ strips of squares and cut them one by one. So the cutting time will be
$$C_h=n+(n+1)\times(1+m)=nm+2n+m+1.$$
If we first rotate the grid (this turn is not counted, as the initial position of the grid is not defined a priori),
than we get the symetrical formula :
$$C_v=nm+2m+n+1.$$
The difference between these two numbers is $C_h-C_v=n-m$. It's greater than $0$ if $n$ is strictly greater than $m$
(the situation shown on the picture). In that case, it would be quicker to start in the position where the longest
side is vertical.
Now, suppose that $mm+1$, $k+1+m+1>m+1$ and
$m+1+n-k>m+1$. Also, it's obvious that $2m+2>geq$. So, in each case, the number of turns is more than $m+1$, which
completes the proof of the proposition, by induction over the size of the grid.\hfill$\Box$
The proposition gives a lower bound for the number of turns, and therefore the cutting time for any $(m+1)\times
(n+1)$ grid. But we already found a cutting plan that gives that exact value. We can then deduce the following
theorem.
\bigskip
{\sl {\bf Theorem.} The minimal cutting time for a $(m+1)\times (n+1)$ grid, where $m