# The Right Triangle Game

I am looking for a deeper understanding, particularly the optimum strategy and the maximum score as a function of grid size, of the following (single-player) game played with an $n$ by $m$ grid: ($6 \times 6$ example)

## Rules

1. Start with a grid made of $n$ by $m$ squares and execute as many moves as you can
2. A move consists of making a single straight cut that cuts off a right triangle with the condition that the cut must start and end on a grid point

## Example 1: “Naive” strategy

The naive strategy consists of always picking the move that cuts off the smallest possible right triangle.

For grids larger than $2 \times 2$, the naive strategy is game over after four moves: ## Example 2: A better try

The following game run, although it starts by cutting off half the grid, contains twenty moves: ## Notes

• Although the examples all use a $6 \times 6$ square grid, I am particularly interested also in non-square rectangular boards (where the grid units are still squares, of course).
• The triangles cut off in the example games are all isosceles. Note that this is not required by the rules!
• Since the smallest triangle that can ever be legally cut off is half of a grid unit, $2nm$ is a trivial upper bound for the maximum score.
• Unrelated to the original question, this single-player game can also be converted to an interesting two-player game: Players alternate making moves; the last player to make a legal move wins.

## The maximum score function

Let $f(n,m)$ denote the maximum score (number of moves) attainable with an $n \times m$ grid.

The following is known about $f$:

$f(n,m) = f(m,n)$ (symmetry)

$f(n,m) \leq 2nm-1$ (see hardmath’s comment)

$f(n,1) = 2n-1$ (see hardmath’s comment)

$f(n,2) = 3n$ (can be obtained with some thinking)

$f(1,1) = 1$ (corollary of above formula)

$f(2,2) = 6$ (corollary of above formula)

$f(3,3) = 11$ (obtained by manual trial and error)

$f(4,4) = 16$ (obtained by manual trial and error, corrected by hardmath’s comment)

$f(n,m) \ge 2\min(n,m) + 3\max(n,m) - 4$ (see hardmath’s comment), in particular

$f(n,n) \ge 5n - 4$

Note that the last bound is actually strict for $1 \le n \le 4$, so this bound (and the associated strategy) might already be the answer to the entire question.