BrainDen.com - Brain Teasers
• 0

# Painting a checkerboard

## Question

You are given a huge white nxn checkerboard and tasked with painting it red, one square at a time. You find the task tedious, so you quit after painting m of the squares red, and then you give the job to your assistant Bob. Bob is not a workaholic either, so "compassionately" you tell him he only needs to paint a square when he finds that it has two sides that border with red squares, regardless of who painted them. That is, Bob cannot quit painting until no white squares having two red borders remain. Clearly by wisely choosing your squares, and if m is large enough, you can compel Bob to paint all of the remaining squares.

Clarifications:

• To border another square an entire side must be shared, not just a corner.
• If two red squares touch diagonally, Bob must paint the white square(s) that they both share a side with.
• If m = 1, or if you've painted squares sufficiently distant from the others, Bob won't have to paint any squares.

Prove there is a least amount of work you must do (smallest m) that makes Bob complete the job.

## Recommended Posts

• 1
6 hours ago, bonanova said:

Clue:

Hide contents

What property of the painted squares (collectively) remains constant as more squares are painted?

Oh, wow.

The total perimeter of painted area remains the same.  For an nxn board, you have a perimeter of 4n, so the same must be true of the initially painted squares.  Since each square is 4 units in perimeter, you need n squares initially painted to make 4n.

##### Share on other sites

• 1
9 hours ago, bonanova said:

Can you prove that's minimal?

Can you think of a necessary property for your red squares?

I can try to put into words why I think it's minimal, but I don't know if it will qualify as a proof.

Some observations:
1. There must be a red square in a rank for that rank to become red.  The same is true of files.
2. You could create a red square in a new rank only if two red squares already exist in different ranks along the same file, which is never more optimal.  The same is true of files.
3. Since we can't add a new rank without giving up a file, the optimal placement is along a diagonal.
4. Any other diagonal other than the long diagonal doesn't cover every rank and file.
5. There are other configurations that still work by manipulating the diagonals, but all of them are n length and all of them cover the same colour square.

##### Share on other sites

• 0

Hey ! I'm a newbie, so yeah still learning, is the answer m = n +1 ? I got it after some practical analysis

##### Share on other sites

• 0
Just now, WorldDev said:

Hey ! I'm a newbie, so yeah still learning, is the answer m = n +1 ? I got it after some practical analysis

Hi WorldDev and welcome to the Den.

Spoiler

That's sufficient; now can you prove it's the lowest.

##### Share on other sites

• 0
7 minutes ago, bonanova said:

Hi WorldDev and welcome to the Den.

Hide contents

That's sufficient; now can you prove it's the lowest.

I actually tried it for a 5x5 and 6x6 checkerboard and found out the lowest general solution, let me see if I could formulate a proof for this...

##### Share on other sites

• 0

I can definitely do it in n by painting either diagonal that begins (and ends) in a corner.

##### Share on other sites

• 0
2 hours ago, Molly Mae said:

Hide contents

I can definitely do it in n by painting either diagonal that begins (and ends) in a corner.

Can you prove that's minimal?

Can you think of a necessary property for your red squares?

##### Share on other sites

• 0
45 minutes ago, Molly Mae said:
Spoiler

There must be a red square in a rank for that rank to become red.  The same is true of files.

Spoiler

Chessboard a2 a4 a6 a8 b1 d1 f1 h1

##### Share on other sites

• 0
7 minutes ago, bonanova said:

Hide contents

Chessboard a2 a4 a6 a8 b1 d1 f1 h1

My point 2 is designed to cover this case (and similar cases).

EDIT: That is, it can be as optimal, but it will never be more optimal.

Edited by Molly Mae
##### Share on other sites

• 0
4 minutes ago, Molly Mae said:

My point 2 is designed to cover this case (and similar cases).

EDIT: That is, it can be as optimal, but it will never be more optimal.

Spoiler

OK.  I misread point 1 as meaning you need n because each rank/file needs an initial red.

##### Share on other sites

• 0

@Molly Mae I gave your description a point and will mark it as solved in a couple days to allow some time to offer a proof.

Spoiler

It depends on a certain geometric property of the initial red squares that, after a little thought, must meet a simple condition. (Since it's a proof about the number of initial squares, the condition applies to an extensive property of the initial squares.)

##### Share on other sites

• 0

A few observations that might lead to a proof:

1. There must be a red square on each extreme rank and file (this can be, but isn't required to be, the same red square for a given rank/file combination) for any nxn.
2. This must also be true for n-1xn-1 (and n-2xn-2, and so on)
3. Since we can always reduce n to 1, there should be no optimal strategy that uses fewer than n red squares for a board that's nxn.

Probably

##### Share on other sites

• 0

I have seen neat puzzles where the answer is flat out obvious but (1) wrong or (2) has a simple proof that hides in the shadows.

This puzzle, and the one about tiling a hexagon with diamonds, are type (2).

##### Share on other sites

• 0

Clue:

Spoiler

What property of the painted squares (collectively) remains constant as more squares are painted?

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.