Jump to content
BrainDen.com - Brain Teasers
  • 0
bonanova

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.

Share this post


Link to post
Share on other sites

14 answers to this question

  • 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
  • 0

Clue:

Spoiler

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

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×