Painting a checkerboard

[bonanova]

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.

[Molly Mae]

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.

[Molly Mae]

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.

[WorldDev]

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

[bonanova]

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.

 

[WorldDev]

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...

 

[Molly Mae]

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

[bonanova]

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?

[bonanova]

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

 

[Molly Mae]

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 January 29, 2018 by Molly Mae

[bonanova]

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.

 

[bonanova]

@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.)

 

[Molly Mae]

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

[bonanova]

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).

[bonanova]

Clue:

Spoiler

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