Minimum tiles for a grid given a few conditions

Question

Today, I came across an exercise in Problem Solving Strategies by Johnson and Herr which I was not sure was the best way to solve it. The problem given was:

Below I drew up a quick sketch of a diagram.

Note that each row and column should be the same height and width, which is not apparent by my sketch (sorry!). Also, there should be a horizontal line ending the last row of tiles.

My line of thinking was that since there was $12$ vertical lines and $9$ horizontal lines, there are $11$ horizontal tiles per row and $8$ vertical tiles per column. Also note that the total number of intersections is given by $12(9) = 108$. (Note I am unsure whether to count the very top line horizontal line as one of the nine lines and the far left line as one of the twelve vertical lines.) Each title has $4$ intersections. Thus the minimum number of tiles to cover the area would be $\frac{108}{4} = 27$ tiles. However, due to there being an odd number of lines ($9$), $24$ tiles would only cover $8$ lines ($96$ intersections). So, to account for those last $12$ intersections, we need to add $6$ more tiles - giving us a total min number of tiles needed being $30$.

Is this the type of logic you would use to solve similar problems to this - or is there a sneakier way perhaps?

Answer 1

Here is a formal proof:

picture in red the lowest right corner, and every other intersection in the form $(2i,2j)$. Two different "red point" are at distance at least $11*2$, so for every "red point" one tile is needed (the farthest two point in a tile are $\sqrt2*12$ apart).

How many "red point" you have? $$\lceil\frac{m}{2}\rceil\times\lceil\frac{n}{2}\rceil$$

So this is a lower bound on the number of tiles used. But you have already show a configuration for witch $30$ (and generally $\lceil\frac{m}{2}\rceil\times\lceil\frac{n}{2}\rceil$) tiles cover each point (so an upper bound).

This number are the same, so you have done.

---

For this class of problem, the solution is always in two part: show a solution that work, and show that you can't do better, so it has to be optimal. Depends on the problem what's the hardest part, sometimes there are hugly costruction, but most of times finding the proof the hard part that require more work. A good rule of thumbs is never use induction for demostrating that the solution is optimal, usually the way is finding some sort fo invariant that hold and reduce the problem to a simpler one (like here, every "red point" one tiles, so tiles $\geq$ red point).

Answer 2

Here's the general formula I came up with:

Given $m$ horizontal lines and $n$ vertical lines, the number of tiles needed to cover the grid is

$\lceil\frac{m}{2}\rceil\times\lceil\frac{n}{2}\rceil$

So with $m=12$ and $n=9$

$\lceil\frac{12}{2}\rceil\times\lceil\frac{9}{2}\rceil=\lceil6\rceil\times\lceil4.5\rceil=6\times5=30$

As far as the method goes, I started with a very simple (1 vertical by 1 horizontal line) case and then expanded it to a larger case (2 vertical by 3 horizontal) and so on. Start with a trivial case, then with a slightly more complex case, and then generalize.