# 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
3. Your score is the number of moves you made

## 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.

• Maybe you could find the maximum for $1\times1,2\times2,3\times3,\dots$ until you have enough to look it up in the Online Encyclopedia of Integer Sequences. Mar 30, 2014 at 11:57
• It suggests a strategy (in the one-player original Q) of shortening the shorter dimension (say $n \ge 2$) down to 2 by a sequence of $2(n-2)$ moves (bisecting each row along a diagonal), then getting $3m$ moves out of the remaining $2 \times m$ shape. Thus $f(n,m) \ge 2n + 3m - 4$ when $m \ge n \ge 2$. Mar 31, 2014 at 12:00
• We can reduce $3\times 4$ to $2\times 4$ in 2 moves, taking off the "top" row by bisection along its diagonal. Mar 31, 2014 at 19:25
• Ah, you mean by slicing off two thin, non-isosceles triangles? True, that works!
– user139000
Apr 1, 2014 at 6:43
• @JensRenders: $f(m,n)\ge2m+3n-4$ was established as a limit by user hardmath. I have verified that equality in the extreme value, i.e. $f(m,n)=2m+3n-4$, holds for $2 \le m \le n \le 10$. Mar 18, 2016 at 16:24

## 1 Answer

Given that the board m x n may not necessarily square, perhaps for the non-square boards, you must use a method that treats it as a non square board. Im implying that some of the triangles that are cut off are likely to not be isosceles due to the different dimensions and in fact the most optimal way may be cutting off triangles in the ratio of the rectangle of sorts.

Another possibility is sectioning the rectangular board into a square and non-square board. Then you use the optimal method for solving the square and then continue to cut off right triangles on the left over non-square section

I hope this provides some insight to this problem