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

## Question

## bonanova

You are given a huge white

xncheckerboard and tasked with painting it red, one square at a time. You find the task tedious, so you quit after paintingnof 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 hasmsides 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 iftwois large enough, you can compel Bob to paintmof the remaining squares.allClarifications:

= 1, or if you've painted squares sufficiently distant from the others, Bob won't have to paint any squares.mProve there is a

amount of work you must do (smallestleast) that makes Bob complete the job.m## Link to comment

## Share on other sites

## 14 answers to this question

## Recommended Posts

## Join the conversation

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