I like to think that I'm good at these combinatorics-kind of questions, but I can't wrap my head around this one. I can follow the construction of the matrix, but I don't understand how you came up with the formula.
Reusing the notation of my post, here's how the formula arises.
The argument based on counting cells that are either row/column good/bad requires the following of the parameter k:
1. k-1 < r/m
2. k-1 < c/n
3. k−1 < cr/(c(m-1) + r(n-1))
1. k <= ceil r m
2. k <= ceil c n
3. k <= ceil cr (c(m-1) + r(n-1))
k <= min (ceil r m) (ceil c n) (ceil cr (c(m-1) + r(n-1)))
* ceil r m = ceil (cr) (cm)
* ceil c n = ceil (cr) (mr)
* min (ceil x y) (ceil x z) = ceil x (max y z)
k <= ceil cr (c(m-1) + r(n-1))
Without knowing anything about k except that k-1 < r/m, I counted how many cells are column-bad for this value of k. By the pigeon-hole-principle argument in the post this is at most c(m-1)(k-1) cells. Similarly, and still knowing nothing about k except that k-1 < c/n, I count how many cells are row-bad for this value of k and see that it is at most r(n-1)(k-1). Combining these two I know that as long as we have k-1 < r/m and k-1 < c/n the number of cells that are either column-bad or row-bad (or both) is at most:
* c(m-1)(k-1) + r(n-1)(k-1)
* c(m-1)(k-1) + r(n-1)(k-1) < rc
And then solve this to get the formula for k. Of course when expositing it in the post, I _start_ with the formula which perhaps makes things seem mysterious at first, but I thought was efficient.
I'd say that the exposition in your post is very fitting for the purpose of proving it. The most elegant proofs are usually not the most enlightening.