I can solve only the square case. The board can be dominated with $\left\lceil \frac{2n-1}{3} \right\rceil$ and this is the minimum. For the rectangular case, I have only a criterion that gives a lower bound: You need at least $\min\left(m, n, \frac{m+n-1}{3}\right)$ pegs. However this is not optimal: 4x6 needs 4 pegs, but the criterion gives only 3.

This problem baffles me because I would think that cmmmrc's bound should be correct. But for example, like cmmmrc says, a $4\times6$ board needs $4$ tokens, while a $5\times8$ only needs $4$. Does anyone see a pattern in the types of boards that don't obey cmmmrc's bound?

Me, of course!! I made a little step further, solving the cases when n-1 pegs are sufficient (n is the minor dimension). It turns out that n x 2n-2 can be covered with n-1 pegs iff n is not 0 (mod 4). n x 2n-1 can never be covered with n-1 pegs. So 4x6, 8x14, 12x22 etc... are cases when my lower bound is not optimal. Moreover some other cases are there when things go bad. 7x9 should be covered with 5 pegs, but this is indeed impossible. My guess is (but is just an impression, I may well be very wrong) that when 3 | n+m-1 and we are not in the square case or in the (n-1)-pegs case, the lower bound is not optimal, and probably one more peg does the trick. Just my guess, beware. M.

I don't why I didn't look before, but Kalva's homepage states that we only need solve the $n\times n$ board. Thus cmmmrc's bound solves the problem. It is still interesting to see if a solution exists for an $m\times n$ board. Maybe this string should be moved to the open problems section.

Assume that $ k$ pegs dominate the entire board, and call "naughty" the squares that are not in a row or column where a peg lies (ie, those that are not dominated horizontally or vertically, but are dominated diagonally). Now, clearly there are $ (m - k)(n - k)$ naughty squares, that we distribute in diagonals $ \searrow\hspace{ - 4.45mm}\nwarrow$, which in turn we number starting from the lower left corner of the board. Clearly, the first and last such diagonals contain at most one square; if the first diagonal contained two squares, the square that is in the intersection of the row of one and the column of the other, lying lower and left, would also be naughty, and its diagonal $ \searrow\hspace{ - 4.45mm}\nwarrow$ would be lower and left from the first one, contradiction - similarly for the last diagonal. The second and next to the last diagonals contain at most two naughty squares, in the intersection of their row and column lie the squares in the first and last diagonals, and so on. Hence naughty squares are covered diagonally in bunches of $ 1,1,2,2,3,3,\dots$, ie, with the first $ 2n - 2k - 2$ pegs we dominate at most $ (n - k)(n - k - 1)$ naught squares. Hence, assuming $ n\leq m$ since otherwise we perform a symmetry around diagonal $ \searrow\hspace{ - 4.45mm}\nwarrow$ leaving the problem unchanged except for reversing $ m,n$, we find that $ (n - k)(n - k - 1) < (m - k)(n - k)$, and we need additionally $ (m - k) - (n - k - 1) = m - n + 1$ pegs to dominate each $ n - k$ naughty squares (since each diagonal contains $ k$ squares dominated horizontally, hence not naughty). Hence the number of pegs satisfies $ k\geq2n - 2k - 2 + m - n + 1$, or $ 3k\geq m + n - 1$ and $ k\geq\lceil\frac {m + n - 1}{3}\rceil$, where $ \lceil x\rceil$ is the least integer larger than or equal to $ x$. Note that this is NOT necessary if $ m$ or $ n$ are less than this value, since then we need just one peg per row or column to dominate the entire board, and no naughty squares exist.

The original problem only asks for you to consider the square case ($m \times m$).