Removing matchsticks

Consider the vertical matches, there are $24$ of them. Every move removes $1$ ( type 1 move ) or $2$ ( type 2 move ) vertical matches. So the upper bound of consecutive moves is $24$ . However any time we perform a type 1 move, we must remove one of the matches from the middle horizontal line. Since there are only $11$ matches in the middle line, we can perform at most $11$ type 1 moves.

---

Suppose you perform $n\leq 11$ type 1 moves, then you are left with $24-n$ vertical matches that you can use to perform (at most)

$\left\lfloor\dfrac{24-n}{2}\right\rfloor=12-\left\lceil\dfrac{n}{2}\right\rceil$

type 2 moves, with a total of

$n+12-\left\lceil\dfrac{n}{2}\right\rceil$

moves, which doesn't get bigger than $\boxed{17}$

---

A possible sequence of $17$ moves:

.

It is possible to make 17 moves , leaving only $57 - 17\times 3 = 6$ matchsticks.

In the top row, remove $\subset$ -shapes from left to right. This takes 11 moves and leaves only one vertical matchstick at the end.

In the bottom row, remove $\cup$ -shapes from left to right. Between each two moves, a single horizontal matchstick at the bottom must be skipped. It takes 6 moves and leaves five matchsticks at the bottom.

---

More than 17 moves is impossible.

Define

• $a$ = number of $\subset$ -shaped moves (or mirror image);

• $b$ = number of $\cup$ -shaped moves in the bottom row and $\cap$ -shaped moves in the top row.

• $c$ = number of $\cup$ -shaped moves in the top row and $\cap$ -shaped moves in the bottom row.

There are three lines of 11 horizontal matchsticks and two rows of 12 vertical matchsticks.

• Effect of moves on the middle line of horizontal matchsticks: $a + c = M \leq 11.$

• Effect of moves on the top and bottom lines of horizontal matchsticks: $a + b = N \leq 22.$

• Effect of moves on the vertical matchsticks: $a + 2b + 2c = V \leq 24.$

Solve this system, so we can analyze the number of moves $(a,b,c)$ in terms of matchsticks $(M,N,V)$ : $\left[\begin{array}{ccc} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 2 & 2 \end{array}\right] \ \left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \left[\begin{array}{c} M \\ N \\ V \end{array}\right]\ \ \ \therefore\ \ \ \left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \frac 13 \left[\begin{array}{ccc} 2 & 2 & -1 \\ -2 & 1 & 1 \\ 1 & -2 & 1 \end{array}\right] \ \left[\begin{array}{c} M \\ N \\ V \end{array}\right].$

Now let $m = 11 - M$ , $n = 22 - N$ , $v = 24 - V$ represent the matchsticks that remain. We have $\left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \frac 13 \left[\begin{array}{ccc} 2 & 2 & -1 \\ -2 & 1 & 1 \\ 1 & -2 & 1 \end{array}\right] \ \left[\begin{array}{c} 11-m \\ 22-n \\ 24-v \end{array}\right] = \left[\begin{array}{c} 14 \\ 8 \\ -3 \end{array}\right] - \frac 13 \left[\begin{array}{ccc} 2 & 2 & -1 \\ -2 & 1 & 1 \\ 1 & -2 & 1 \end{array}\right] \ \left[\begin{array}{c} m \\ n \\ v \end{array}\right].$

Note that $c = -3 - \dots$ : however, $c$ cannot be negative. This means that $\frac 1 3(m - 2n + v) \leq -3\ \ \ \therefore\ \ \ \ 2n - m - v \geq 9.$ We wish to minimize $n, m, v \geq 0$ ; clearly, this requires $n = 5$ and either $m = 1$ or $v = 1$ .

Thus we have shown that we end up with at least 5 horizontal matchsticks in top or bottom line; there cannot be more than 17 moves.

To finish up, choosing $n = 5$ and $v = 1$ , we get $\left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \frac 13 \left[\begin{array}{ccc} 2 & 2 & -1 \\ -2 & 1 & 1 \\ 1 & -2 & 1 \end{array}\right] \ \left[\begin{array}{c} 11 \\ 17 \\ 23 \end{array}\right] = \left[\begin{array}{c} 11 \\ 6 \\ 0 \end{array}\right].$ This is the situation I described at the top of my solution.

Alternatively, with $n = 5$ and $m = 1$ , $\left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \frac 13 \left[\begin{array}{ccc} 2 & 2 & -1 \\ -2 & 1 & 1 \\ 1 & -2 & 1 \end{array}\right] \ \left[\begin{array}{c} 10 \\ 17 \\ 24 \end{array}\right] = \left[\begin{array}{c} 10 \\ 7 \\ 0 \end{array}\right].$ Challenge: Can someone describe the solution corresponding to these values?

There are 11 horizontal matches that are "in the middle" (i.e. are not at the bottom or top) and there are 24 vertical matches. So those two groups have a combined total of 35 matches, out of which at least 2 must be removed by each move, which proves that there cannot be more than 17 moves.

My method for making 17 moves was similar to Marco Brezzi's.

Just induct it.