\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 $m<n$ and let's study the other cutting plan introduced in the previous section, with the new rule.
It goes like this :

\begin{itemize}
\itemb Cut along the first vertical line from the left : $1$ time unit.
\itemb Rotate the left hand strip and cut it into $m+1$ unit squares : $1+m$ time units.
\itemb Rotate the right hand grid and cut it into $m+1$ strips : $1+m$ time units.
\itemb For each of the $m+1$ strips, rotate it and cut it into $n$ unit squares : $(m+1)(1+n-1)$ time units.
\end{itemize}

The cutting time is therefore 
$$1+2\times (1+m)+n(m+1)=nm+2m+n+3.$$

This is obviously greater than $C_v$. 

In fact, it may be noticed that the number of cuts is the same as in the previous section, the difference being in the
number of turns. Indeed, if we look at the situation where the longest length is vertical and we start by doing all the
vertical cuts, there are $mn+m+n$ cuts and $m+1$ turns (one for each strip) and $C_v=mn+m+n+m+1$. So our problem is
just to find the minimal number of turns. 

\bigskip

{\bf Proposition.} Any method to cut-out completely a $(m+1)\times (n+1)$ square grid involves at least
$\textrm{Min}(m,n)+1$ turns.

\bigskip

{\sl Proof.} First, consider a $1\times k$ strip of $k$ squares, in a vertical position, for any natural number $k$
greater than $1$. Obviously, to cut it out, we need to turn it once first. So the property is true in that case. 

Now, assume that the property is true for any $(i+1)\times (j+1)$ square grid smaller than $(m+1)\times (n+1)$, and
also that $m<n$. Then we have to prove that the number of turns is at least $m+1$.

We can decide to put the grid in a vertical position and start cutting that way. The first cut will
be along one of the vertical lines, so that there will be a $(k+1)\times (n+1)$ grid on the left and a $(m-k)\times
(n+1)$ on the right, with $0<k<m$. Each strip is still in a vertical position, as $k<m<n$ and $m-k<m<n$,
so, according to our induction hypothesis, we will need at least $\textrm{Min}(k,n)+1=k+1$ turns for the left-hand
part and $\textrm{Min}(m-k-1,n)+1=m-k$ for the other. So the total number of turns for the whole grid is at least
$$k+1+m-k=m+1.$$

But we can also decide to start with the grid placed horizontally. Then, the first cut will be along one of the shortest
lines, so that there will be a $(m+1)\times (k+1)$ grid on the left and a $(m+1)\times (n-k)$ on the right, with
$0<k<n$. Let's look at the $(m+1)\times (k+1)$ grid. If $k\leq m$, than according to our
induction hypothesis, the minimal number of turns to cut it is $\textrm{Min}(k,m)+1=k+1=k$. If $m<k$, than the
minimal number of cuts is $\textrm{Min}(k,m)+1=m+1$. Now, let's look at the $(m+1)\times (n-k)$ grid. If
$n-k-1\leq m$, than according to our induction hypothesis, the minimal number of turns to cut it is
$\textrm{Min}(n-k-1,m)+1=n-k$. If $m<n-k-1$, than the minimal number of cuts is $\textrm{Min}(n-k-1,m)+1=m+1$. The
total number of turns is given in the table below :
\begin{center}
\begin{tabular}{c|c|c|}
 & If  $k\leq m$ &  $m<k$ \\
\hline
 && \\
If $n-k-1\leq m$ & $k+1+n-k=n+1$ & $m+1+n-k$ \\
 && \\
\hline
 && \\
If $m<n-k-1$ & $k+1+m+1$ & $m+1+m+1=2m+2$ \\
 && \\
\hline
\end{tabular}
\end{center}

We assumed that $m<n$, and from its definiton $0<k<n$. Therefore, we can say that $n+1>m+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<n$, is $$mn+2m+n+1.$$
To cut the grid in the minimal time, start by putting the grid vertically, cut along along the vertical lines, then
turn each strip of squares and cut them off one by one.}

\bigskip


{\sl Proof.} From the previous theorem, we know that the number of turns is at least $m+1$. Also, from the previous
section, the number of cuts is $mn+m+1$, so the cutting time cannot be less than the sum 
$$mn+m+1+m+1=mn+2m+n+1.$$
As we've seen at the beginning of this section, the cutting plan described in the theorem gives that exact cutting
time. So the minimal cuttin time is $mn+m+1+m+1=mn+2m+n+1.$\hfill$\Box$


\end{document}
