93

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:

enter image description here ($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:

enter image description here


Example 2: A better try

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

enter image description here


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.

  • 7
    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. – Gerry Myerson Mar 30 '14 at 11:57
  • 1
    Each successive remnant of the board is necessarily a convex shape, produced from the previous stage by "a single straight cut that... must start and end on a grid point". If we don't count removing a single final right triangle with such a cut, then the trivial upper bound is really $2nm-1$, attainable if one of the dimension is $1$. – hardmath Mar 30 '14 at 14:01
  • 5
    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$. – hardmath Mar 31 '14 at 12:00
  • I'm not sure I understand you correctly. Let's say we have a $3 \times 4$ grid. There is no way of shortening the shorter dimension ($3$) down to $2$ without affecting the other dimension as well. –  Mar 31 '14 at 16:11
  • Note also that your formula implies that $f(4,4)\geq 16$, while my trials strongly indicate that $f(4,4)=15$. –  Mar 31 '14 at 18:03
  • 3
    We can reduce $3\times 4$ to $2\times 4$ in 2 moves, taking off the "top" row by bisection along its diagonal. – hardmath Mar 31 '14 at 19:25
  • 4
    Ah, you mean by slicing off two thin, non-isosceles triangles? True, that works! –  Apr 01 '14 at 06:43
  • 1
    Question: You say that the cut must start and end in a grid point, but ¿must that grid point be in the shape you have cut so far, or can it be outside? – gonthalo Sep 03 '15 at 18:08
  • 1
    I've verified $f(m,n) = 2m + 3n - 4$ as a strict limit for $2 \le m \le n \le 10$ via exhaustive search. – Frentos Dec 16 '15 at 03:34
  • @Frentos what do you mean by "strict limit"? Do you mean $f(m,n)\geq2m+3n-4$ – Jens Renders Mar 18 '16 at 14:44
  • 3
    @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$. – Frentos Mar 18 '16 at 16:24
  • Could you maybe set up a recurrence relation by figuring out the relationship between $f(m,n)$ and $f(m,n+1)$? – Franklin Pezzuti Dyer Apr 21 '17 at 20:45
  • @FranklinPezzutiDyer Well for $2\le m \le n$, the previous comments did observe a recursive strategy that gives $f(m,n)\ge 2+f(m-1,n)$. But can anyone prove this strategy is optimal? (Does the equality hold?) Apply it until $m=2$ to use $f(2,n)=3n$, which finally yields $f(m,n)\ge 2(m-2)+3n$ as already discussed. The problem now is either proving the equality holds (strategy is optimal), or finding a counter-example (a better strategy). – Vepir Apr 04 '20 at 22:05

1 Answers1

1

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

Stone
  • 394