Jump to content
BrainDen.com - Brain Teasers
  • 0

Painting a checkerboard


bonanova
 Share

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.

Link to comment
Share on other sites

14 answers to this question

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.

Link to comment
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.

Link to comment
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.)

 

Link to comment
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

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...