Discrete mathematics - inductive proof with an arbitrarily sized matrix I'm studying discrete mathematics and this week's homework (which is supposed to be about induction) included this question:
Let $M$ be a $m \times n$ - ordered matrix whose cells are only zeros or ones and which contains at least one cell whose value is $1$.
A cell whose value is $1$ will be called "good" if one or more of the following criteria are met:


*

*The cell is in the first row of $M$

*The cell is in the first column of $M$

*The cell above it and the cell to the left of it are both $0$ - that is, for the $(i,j)$ cell to be "good", the $(i-1,j)$ and $(i,j-1)$ cells must both be $0$ (assuming $i,j \neq 1$) .


Prove that $M$ contains at least one "good" cell.
Hint: prove inductively that for every $s \geq 2 \in \mathbb{N}$ , if $m+n=s$ then $M$ has a good cell.
~
I thought about it for a while and realized that the first $1$ in the first non-zero row of $M$ will be a "good" cell regardless of the matrix's dimensions. Now, I know that stating this fact doesn't constitute an acceptable proof; my trouble is finding a way to prove it inductively.
Using the hint provided in the question I surmised that the base case for an inductive proof of this argument is a $1 \times 1$ matrix whose only cell contains $1$. The inductive argument would then be:
If a matrix $M_{m \times n}$ where $m+n = k-1 \geq 2$ contains a "good" cell, then a matrix $M'_{p \times q}$ where $p+q = k > 2$ also contains a good cell.
I started the proof itself like so:
Let $k > 2 \in \mathbb{N^+}$ and let $M_{m \times n}$ be a matrix as described in the problem where $m+n=k-1\geq2$ . We'll assume this matrix contains a "good" cell. We'll add a row or column to $M$ arbitrarily and prove that the resulting matrix $M'_{p \times q}$ where $p+q = k > 2$ also has a "good" cell in it.
Let $i,j \in \mathbb{N^+}$ so that the $(i,j)$ cell in $M$ is "good". Upon adding a row or column to the matrix $M$ , one of two possibilities may be true:
1) The $i,j$ cell in $M'$ is still "good", which means the row or column that was added to $M$ was added after the $i$ row or after the $j$ column, respectively.
2) The $i,j$ cell in $M'$ is not good, which means that either the cell above it or to the left of it is now $1$.
~
The second possibility is where things start getting messy (for me, at least) because since the row or column was added to $M$ arbitrarily there really is no way to use the placement of the "good" cell in $M$ to locate the "good" cell in $M'$...
Either I'm approaching this problem the wrong way or there's something here I'm missing, but either way I'm pretty stumped as to how to proceed from there. Does anyone have any ideas?
 A: The matrix $M$ is a function $M:\{1,\ldots,m\}\times\{1,\ldots,n\}\to\{0,1\}$.  Define an order $<$ on $\{1,\ldots,m\}\times\{1,\ldots,n\}$ as
$$(i,j)<(k,l)\quad\text{if either }(i<k)\text{ or }(i=k\text{ and }j<l)$$
This gives a total order on $\{1,\ldots,m\}\times\{1,\ldots,n\}$ and the elements can be listed as $$(1,1)<\cdots<(1,n)<(2,1)<\cdots<(2,n)<\cdots<(m,1)<\cdots<(m,n)$$
Now given the matrix $M$, if every $M(i,j)=0$, then $M=0$.  So suppose $M\ne0$.  Let $D=\{(i,j):M(i,j)=1\}$.  Then since $M\ne0$, we have $D\ne\emptyset$.  Let $(s,t)$ be the smallest element in $D$ with respect to the given order $<$.  Such an element exists and is unique since $<$ is a total order on a finite set $\{1,\ldots,m\}\times\{1,\ldots,n\}$.
If the elements $(s-1,t),(s,t-1)$ exist, that is, if $s>1$ or $t>1$ (respectively), then clearly $(s-1,t)<(s,t)$ and $(s,t-1)<(s,t)$.  So by the 'smallest element' choice, $(s-1,t),(s,t-1)\not\in D$.  So $M(s-1,t)=M(s,t-1)=0$ and hence $(s,t)$ is good.
Alternate Solution using Induction:
We fix $n$, the number of columns and induct on $m$, the number of rows.  The result is obvious for a nonzero $1\times n$ matrix (which is a vector), since the first nonzero cell will be a good cell.  Suppose the result holds true for any nonzero $m\times n$ matrix.
Now let $M$ be an $(m+1)\times n$ matrix such that $M\ne0$.  Let $M'$ be the matrix obtained from $M$ by deleting the $(m+1)$-th row and let $R$ be the $(m+1)$-th row of $M$.  So $M'$ is an $m\times n$ matrix.  If $M'=0$, then $R\ne0$ since $M\ne0$ and hence by base case, $R$ has a good cell, say $(s,t)$.  (Note that $R$ can be naturally identified with a vector.)  Since $M'=0$, it follows that $(s,t)$ is also a good cell of $M$.
Now suppose $M'\ne0$. Then by induction hypothesis, $M'$ has a good cell, say $(s,t)$.  Then again $(s,t)$ is a good cell of $M$.
Hence by induction, $M$ has a good cell.
