Painting a Checkerboard

Question

I love checkers - but I've played it so much that the color of my board is faded and dull. Today, I resolved to paint it. Unfortunately, I slipped and fell :(

Now there's paint all over my checkerpieces!

I only have 5 pieces left - the others fell down the couch somewhere. Could you help me paint my board? I want to paint the largest area possible with my 5 pieces.

The Puzzle

The Rules

1. Each piece can only move once
2. A move consists of hops over orthogonally (i.e. horizontal or vertical, not diagonal) adjacent pieces into empty squares.
3. You can only hop over one piece at a time (you can't hop over two pieces in a row)
4. Each move can consist of as many or as few hops as wanted and possible, and it is perfectly valid to double back on yourself.
5. Once a piece is done moving, it stays on the board and can continue to be hopped over.

The Goal

The goal is to paint as many squares of the checkerboard as possible. Every square that was ever in contact with a piece is considered painted - i.e. the starting square of a piece and every square that it hopped to.

You can choose the starting position of the pieces and the sequence of moves. (Two pieces can't start in the same position though)

Example

This solution paints 8 squares using 4 pieces. I used black to represent unmoved pieces, and white to represent pieces that have already been moved. The numbers are there to help you understand the sequence of happenings. Note that the second piece hopped twice during its move, with the second hop being a return to its starting place.

Assessment Criteria

I'll accept the answer that gets the farthest along in this list of criteria:

• Achieves the best solution
• Shows that their solution cannot be improved upon
• [Bonus] Generalizes their solution to arbitrarily many starting pieces - just in case I find the pieces that fell down the couch.

Extras

• You can assume the checkerboard is arbitrarily large.
• You do not need any calculations to do this, merely "elegant observations". (Even for the bonus problem)
• Checkers is normally played diagonally, but here pieces move orthogonally - this doesn't affect the puzzle. Can you see why?
• This problem originates from past me being bored during lockdown. I know the solution to the problems posed here, but I've not been able to solve it for most other grids (for example a hex grid) so if you enjoyed this puzzle and feel like setting a harder challenge for yourself, try doing it on a different grid.

Answer 1

The optimum is

17 = 2 x (3+1) + 3 x (2+1)

achieved by

    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . 5 . . .
    . . 3 2 . . . .
    . . 1 4 . . . .
    . . . . . . . .
    . . . . . . . .

    . . . . . . . .
    . . . . 5 . . .
    . . . . 3 . . .
    . . 1 4 5 4 5 .
    . 2 3 2 3 . . .
    . 4 1 4 1 . . .
    . . 3 2 . . . .
    . . . . . . . .
 

Note that 1 and 2 return to their starting squares at the end of their moves while 3 and 4 end their moves top and right of 5.

Proof of optimality:

Checkers sitting on a white square can only hop over checkers sitting on a black square and vice versa; neither can change the colour of square they sit on. No piece can reach more than k+1 squares where k is the number of pieces sitting on squares of the other colour (use, for example, @thisIs4d's colouring to see this). If the total number N of pieces is sat on j white squares and k black squares (j+k=N) then this gives the upper bound k(j+1) + j(k+1) which is maximised by the most even split of N.

Answer 2

Maximum number of colored squares in $8$ x $8$ checkerboard with $5$ colored pieces is:

$17$

Let us transform the question. First, let us color each cell of the board as below:

Note: each sub-grid of size $2$ x $2$ contains four distinct colors: Red, Green, Blue, Yellow.

Let us assume that all the squares visited by any checker piece become BLACK. So now the question becomes to maximize the number of BLACK squares on the board.

Key observations:

A checker piece in a square with color $X$, will always remain in a square with color $X$ after any number of hops

Two colors are either connected horizontally, vertically or diagonally (only one of these). This relation between any two of the four colors is always fixed.

If the squares are of same color, or are diagonally related, then checker piece in one square cannot jump over the other square.

Initially, let the $5$ checkers be placed on $X$ distinct type of colored-squares on the board. Then we have following $4$ cases:

(Note: the word "hop" in following discussion refers to hopping over a new checker piece which colors a new square not colored before)

$X$ = 1:

Then maximum number of BLACK squares is:

$5$. Since all $5$ are of same color, none of them are adjacent. Hence, no new BLACK squares apart from the initial squares.

$X$ = 2:

Upper Bound is:

$17$. Let $(X, 5-X)$ be color scheme, then max $2X(5-X)$ hops are possible, i.e. $2$ x $3$ x $2$ = $12$ hops. So upper bound is $5+12=17$

$X$ = 3:

Upper Bound is:

$17$. If color scheme is $(3, 1, 1)$ then for upper bound would be $3$ x $2$ + $1$ x $3$ + $1$ x $3$ + $5$ (intial) = 17. If $(2, 2, 1)$ again upper bound would be $2$ x $4$ + $1$ x $4$ + $5$ = 17

$X$ = 4:

Upper Bound is:

$17$. Color scheme is $(2, 1, 1, 1)$ say colors are $($a, b, c, d$)$. Then $a$ would have atmost 2 hops each, giving 4 hops, among b,c,d two would have atmost 3 hops, and the remaining one would have 1 hop. So, again $2$x$2$ + $2$x$3$ + $1$x$2$ + 5 = 17.

For the General Problem if $X=2$, then the maximum number of colored squares is:

$3N-2$, with all checkers aligned in a line, and direction of $N-1$ checkers is right, and only $1$ checker hops left.

Proof By Induction:

For 2 checkers and 2 colors, we have 4 colored squares at max, which forms the base case. Let the claim be true of $K$ checkers. When we have $K+1$ checkers, it is always bettter to keep all in one line (otherwise different lines would each create max $3z-2$ (using the inductive hypothesis) and would sum up to less than $3(K+1)-2$. If we assume most of the checkers move right, then the rightmost checker would have moved the last by moving right by 1 hop, covering 2 squares. If we ignore this checker, then on the left we have $K$ checkers with atmost $3K-2$ colored squares. So the rightmost of these can still hop over the $K+1$$^{th}$ checker, giving additional $1$ square. $K+1^{th}$ checker can hops atmost once, giving additional 2 squares. This gives $+3$ increment at the max $3(K+1)-2$, and can be achieved by placing the rightmost to-be-moved checker adjacent to the $K^{th}$ moved checker.

For $N \le 4$, the following results:

Note that dividing $5$ into parts of $2$ and $3$ ensures only $11$ colored squares.

If you observe, $N = 4$ is a special case, because:

The flower pattern can tessellate an infinitely large checkerboard. Which suggests there's a pattern modulo $4$. Such a tessellation can imply all squares within the boundary are covered. It looks likely to have as many colored squares with almost equal number of checkers on them.

Diagonal Movements in Checkers won't change the results because:

If we represent every square by its center, then rotating the plane (which had diagonal movements) by $45^{\circ}$ about any point would bring us back to the original plane (with orthogonal movements, only distance between centers have increased by factor of $\sqrt{2}$, but relative positions are the same) preserving every aspect of the coloring process.

Answer 3

Since it's been a week, and the main puzzle was answered by @loopy-walt, I figured I should post the answer to the bonus question. I won't show you the setup that achieves the optimal painting for each n, but if you want a hint:

My solution looks like a chicken with a very long tail, with the length of the tail increasing as n increases. (But of course I'm sure other solutions exist too).

When trying to find the upper bound, most people (including me) would probably first frame the problem as:

Given a piece, what is the most amount of other pieces it can jump over?

However, it is much more productive to think about the problem from the exact opposite perspective:

Given a piece, what is the most amount of pieces that can jump over it?

Thinking about it, we should realize that the answer is:

4 - it can be jumped once horizontally and once vertically before moving, and once horizontally and once vertically after moving. Of course, it could be jumped more than 4 times but those jumps wouldn't paint any new squares and that's really what we're after.

Since each piece automatically paints its starting square, that gives us a (still not tight) upper bound of

5n

We can immediately tighten it to:

5n - 6, because the first piece cannot be jumped before moving (-2 potential paints) and the second square can only be jumped once before moving (-1 potential paints), and a similar argument applies to the last two pieces being jumped after moving.

This is still not tight - and it is here that we come to the logic of @thisis4d, who noticed that (spoiler so big because there's a picture in it):

You can color the checkerboard into 4 colors - and each piece will never land on a square with a different color than its starting square This also limits which pieces can jump over which - a piece can never jump over a piece that started diagonally from it.

We can use this to get our final bound of:

5n-8. Suppose our first piece jumps over the second and the third. Then, the second and third must be of either the same color or diagonal colors - which can't jump over each other! So then the third piece can only be jumped once before moving, one less than the optimum. So our coloring actually prevents us from painting one piece that we could have before (-1 painted square), and we get an additional -1 painted square by using this exact same logic on the last three pieces as well.

We can then look at @loopy-walt's answer to see that this bound coincides with their bound, but it is tighter than theirs for the n>5 case. Constructing examples that achieve this bound for the n>5 case is left as an exercise to the reader, but I assure you it is possible.

Answer 4

Building off of @thisIs4d's solution, I was able to reach:

16 Painted squares

The numbers indicate the order in which the pieces move, and the black squares are the painted squares. Read left-to-right, top-to-bottom.