15
$\begingroup$

Suppose we have a 3x3 board. On this board, several squares are empty and several squares are filled with pieces. A legal move on the board is made using the same idea as taking in checkers: one piece jumps over another one to an empty square and takes that piece. This move can be made horizontally, vertically and diagonally. Below is an example of a legal move made vertically.

enter image description here

What is the maximum number of pieces you can put on the board such that you can make legal moves until there is only one piece left?

$\endgroup$

2 Answers 2

22
$\begingroup$

The number is

6

Proof:

First, observe that no matter what the move the total number of corners occupied does not change. In the desired final position there being only one piece left at most one corner can be occupied and at least three had to be empty from the very beginning. Therefore at most 6 pieces can be placed.

Conversely. Putting a piece everywhere except for three corners we can easily clear the board by making 4 jumps along the boundary and then one diagonal. Therefore at least 6 pieces can be placed.

$\endgroup$
3
  • 1
    $\begingroup$ Blast! I missed diagonally and spent the last 15 minutes trying to write how six was unachievable.+1 $\endgroup$
    – hexomino
    Commented Jan 14 at 22:44
  • $\begingroup$ @hexomino Funny, I, too, nearly missed it. Maybe it's because, traditionally it is not allowed. $\endgroup$ Commented Jan 14 at 22:48
  • $\begingroup$ This is a very elegant answer! If diagonally is not allowed, the maximum number is indeed lower. Then it is actually quite easy to solve if you go in reverse: starting from one piece, make reverse moves until nothing is possible anymore. If diagonally is not allowed, this does not give that many branching possibilities and can be easily checked by hand. $\endgroup$
    – Ocelot
    Commented Jan 15 at 13:48
8
$\begingroup$

To more clearly describe which square I'm talking about I'll be referring to them with up, down, left, right and center like this:

UL U UR
CL C CR
DL D DR

First of all, a piece placed in the corner cannot be jumped over, and it can only jump to another corner, so there can only ever be one piece in the UL, UR, DL and DR squares, this limits the maximum amount of pieces to at most 6, placed in U, CL, CR, D, C and one of the remaining squares
The four possible boards this leaves can all be solved easily

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.