Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bonanova

Question

I have invented magic paint that works on square arrays of squares, like checkerboards.

Here's how it works:

If a square has two or more painted neighbors, it becomes painted automatically.

Neighbor squares are those who share a side: each square has at most 4 neighbors.

If I paint the diagonal squares, then, since all the squares that border a diagonal square

also border another diagonal square, the bordering squares get automatically painted

and that creates a new, fatter diagonal.

As this process continues, the entire square eventually becomes painted.

Can you get an entire 8x8 checkerboard automatically painted, using my magic paint,

by initially painting fewer than 8 squares?

If so, specify the initial 7 [or fewer] painted squares.

If not, can you prove it's impossible?

Share this post


Link to post
Share on other sites

Recommended Posts

  • 0
Guest

no it is not possible, for a row of squares either horizontally or vertically to be painted at least one square in the row has to be painted so the most efficient way is the one that you mentioned painting a diagonal line making sure that every row horizontally and vertically have a painted square in them equalling 8 painted squares.

Share this post


Link to post
Share on other sites
  • 0
Guest
wouldn't this work?

untitled.bmp

Alyanna thank you, yours will not fill in the entire outside ring leaving them unpainted the light purple = your six and the light blue the magic paint, but by adding the black box at the end you can pick up all outside boxes like this:

post-5716-1217537760_thumbjpg

I did not see this until your post so i retract my last guess and now say 7 would work...

Share this post


Link to post
Share on other sites
  • 0
Guest
wouldn't this work?

untitled.bmp

I dont think so but this would

edit: this wouldn't work.. I think you need 8 squares for it to work..

Edited by taliesin

Share this post


Link to post
Share on other sites
  • 0
Guest
I dont think so but this would

edit: this wouldn't work.. I think you need 8 squares for it to work..

I believe you are right. :) I've tried every way I can think of. 8 seems to be it.

Share this post


Link to post
Share on other sites
  • 0
Guest

nvm, i can not do it either

edited for stupidity

Edited by finance_it

Share this post


Link to post
Share on other sites
  • 0
Guest

this is the same as what I posted right after your first post Alyana, without the other colors i was using to check myself, i do believe it will work with only 7.

I tried that too. You end up with something like this...

untitled2.bmp

Share this post


Link to post
Share on other sites
  • 0

OP's question looks solved to me at 8. How 'bout a corollary? How many squares can you paint initially with Bona's paintbrush and still not cover the entire board? I know you can paint at least 24 and not cover it. Can someone do better?

edit:Never mind-that's dumb, too. All you have to do is look at the solutions that didn't work to see that its at least 56.

Edited by HoustonHokie

Share this post


Link to post
Share on other sites
  • 0
Guest
I believe you are right. :) I've tried every way I can think of. 8 seems to be it.

It seems like you need at least as many as there are in the side length of the board. I've been messing around with 3x3 and 4x4, and I can't find a way to fill them with less than 3 and 4 respectively. Part of the problem is that you can't end up with painted squares outside the boundary of your initial placement.

What I mean is that after you choose which squares to paint initially, draw the smallest rectangle you can that will contain all of the squares you painted. No square outside this box will ever be painted by the magic paint. So you have to simultaneously span your desired width and height while also allowing your squares to "procreate." So if there are no painted squares in row 8 to start, there will never be any painted squares in row 8.

It's fairly clear by now how much Bonanova likes proofs, and this is not a proof, but it some observations I made about the problem... :unsure:

Share this post


Link to post
Share on other sites
  • 0
Guest

Sorry, off topic. How are you guys putting the images right in the post. Are you saving it somewhere and using code?

Share this post


Link to post
Share on other sites
  • 0
Guest
Sorry, off topic. How are you guys putting the images right in the post. Are you saving it somewhere and using code?

I did this with my word puzzles. Once you attach something, you can put it directly into the post through the drop down menu above the upload button. Click on the image on the far right of your attachement, and it's in your post! ^_^

Edited by Frost

Share this post


Link to post
Share on other sites
  • 0
It seems like you need at least as many as there are in the side length of the board. I've been messing around with 3x3 and 4x4, and I can't find a way to fill them with less than 3 and 4 respectively. Part of the problem is that you can't end up with painted squares outside the boundary of your initial placement.

What I mean is that after you choose which squares to paint initially, draw the smallest rectangle you can that will contain all of the squares you painted. No square outside this box will ever be painted by the magic paint. So you have to simultaneously span your desired width and height while also allowing your squares to "procreate." So if there are no painted squares in row 8 to start, there will never be any painted squares in row 8.

It's fairly clear by now how much Bonanova likes proofs, and this is not a proof, but it some observations I made about the problem... :unsure:

Your post is very nearly a proof - it asserts all the right points. ;)

All you need to do is include an observation about what happens

whenever a square is automatically painted, and you have a proof.

Anybody see what that statement is?

Share this post


Link to post
Share on other sites
  • 0
Guest
Your post is very nearly a proof - it asserts all the right points. ;)

All you need to do is include an observation about what happens

whenever a square is automatically painted, and you have a proof.

Anybody see what that statement is?

The relation ship between, initially painted squares (i) and maximum squares(p) is: p = i^2, this is achieved by painting on the diagonal of a square ( or every second square of the perminitor of two sides of a rectangle).

Because of this to fill 64 squares (p=64), you can solve to get the answer of 8.

Therefore you need 8 initially painted squares, which are the diagonal throught the middle of the square.

With only 7 initially painted squares (i=7), the maximun number of painted squares is 7^2 or 49, which we have proven multiple times through pratice.

Any comments on my proof?

Share this post


Link to post
Share on other sites
  • 0
The relation ship between, initially painted squares (i) and maximum squares(p) is: p = i^2,

this is achieved by painting on the diagonal of a square ( or every second square of the perminitor of two sides of a rectangle).

Because of this to fill 64 squares (p=64), you can solve to get the answer of 8.

Therefore you need 8 initially painted squares, which are the diagonal throught the middle of the square.

With only 7 initially painted squares (i=7), the maximun number of painted squares is 7^2 or 49, which we have proven multiple times through pratice.

Any comments on my proof?

Hi taliesin,

It's close, maybe it's complete.

Consider:

You've given procedures for painting i2 squares from i initially painted squares.

I think it's clear the procedures work for arrays of any size. So you proved i initial squares are sufficient.

And you've shown - by looking at all the cases - that 7 initial squares can't paint an 8x8 array.

You just need so show that holds for arrays of any size. Maybe you did ...

Here are two other approaches:

  1. What happens [or doesn't happen] when a square is automatically painted?
    There is a particular answer to this question that will lead to a proof for arrays of any size.
    In particular for arrays that are so large we can't explore all the possibilities.


  2. Observe that it requires at least 2 initially painted squares to paint a 2x2 array.
    Then prove that if it's true for an nxn array it must also be true for an [n+1]x[n+1] array.
    [Proof by induction.]

Share this post


Link to post
Share on other sites
  • 0
What happens [or doesn't happen] when a square is automatically painted?

There is a particular answer to this question that will lead to a proof for arrays of any size.

In particular for arrays that are so large we can't explore all the possibilities.

Not sure if this is what you were going for, but it's what I thought of when I read your hint.

In order for a square at coordinates xn,ym to be painted, two of four other squares have to also be painted:xn-1,ym; xn+1,ym; xn,ym-1; or xn,ym+1. Now, if N is the largest x coordinate you paint initially and M is the largest y coordinate you paint initially, it will be impossible to paint another square with x=N+1 or y=M+1, because the farthest you can reach is N,M. Why? In order to paint an exterior square (N+1,y or x,M+1), three of the four potentially required squares are not available, and so we're upwardly bounded at N,M. Similarly, if your smallest x and y coordinates are P and Q, respectively, you can't automatically paint a square with x and y coordinates less than P and Q. So our array of potentially painted squares is bounded in the x-y plane by the x-y coordinates of the initially painted squares.

The other thing you find is that the four squares listed above are connected to each other diagonally. I'm probably dancing all around the proof, but it should be possible to show that the most efficient way to paint an entire array from P,Q to N,M is to start with squares which extend the full range of P,Q to N,M and are all connected to each other diagonally. So you could start at P,Q and proceed diagonally up and to the right until you reach x=N or y=M, then turn 90 degrees and keep doing the same until you've hit the boundary on the other axis. In fact, if there is a gap in the diagonal, two smaller arrays are created, each with their own P,Q and N,M, and unless P2,Q2 is less than N1,M1, the two arrays will be independent and you'll never be able to paint the whole array from P1,Q1 to N2,M2.

Share this post


Link to post
Share on other sites
  • 0
Guest
[*]Observe that it requires at least 2 initially painted squares to paint a 2x2 array.

Then prove that if it's true for an nxn array it must also be true for an [n+1]x[n+1] array.

[Proof by induction.]

Edit: careful between the varible x[/] and times symbols ( x )

For an array of x x y there are 2(x+y) unpainted squares which border a painted square. When adding a square, for each array edge which borders the newly inserted square; we can extend the edge of the array by one square, increaseing it by x bordering the x edge, or y when bordering teh y.

So by adding inserting a square on the extended x edge of the array x x y, the new array will become (x+1) x y, hence increasing the count of painted squares by x.

The most effiecent way to add a square is to place it in a position where it borders as many squares of the array as possible, this is achieved by placing it on its extended corner (a square which borders both x and y); in which case it borders with two array edges. In this case the array size will increase to (x+1)x(y+1)+1. The +1 is to count for the added square which is not a part of either edge. This will increase the size of the array by x + y +1

Arraging this into a formula you get

P() = the number of painted squares

x = x length

y = y length

P(x+1,y) = y + P(x,y) ; when adding on the x axis

if the new square is added on an extended corner a different formula applies

P(x+1,y+1) = y +x + 1 + P(x,y)

if using the formula on a square where x=y it can be simplified to

P(n+1) = 2n + 1 + P(n) , where n = x;

this proves that the squence hold true for all posible numbers of x,y

Using the formula for most efficent painting of a a square and the maximum we can prove that the maximun number of squares we can paint

P( n + 1 ) = 2n +1 + P( n )

this can be written as

P( n ) = 2(n-1) + 1 + P(n - 1)

asmuning P( 0 ) = 0 we can rewrite as

P( n ) = [sigma][x=1 -> n ] 2x - 1

which is the series of square numbers

P( n ) = n^2

Inserting 7 (we are allow to use at most 7 squares)

P ( 7 ) = 7^2

p ( 7 ) = 49

the most painted squares we can get from 7 is 49.

and reversing the equation

P( n ) = n^2

sqrt( P( n ) ) = n

P( n ) = 64 (froma 8x8 square board)

sqrt( 64 ) = 8. therefore we need at least 8 to make a square 64 squares.

These calculation can also be done using the first formula

P(x+1,y) = y + P(x,y)

for a rectangluar array

Share this post


Link to post
Share on other sites
  • 0

Kudos to the effort put into this proof. B))

I think what's been said shows that the paintable area lies within

the smallest rectangle that contains the initially painted squares.

OK - that's not a spoiler, since I think everyone who's posted has

said it, or at least realized it.

Now. How does a consequence of that fact get to the proof?

Relate a fundamental property of that rectangle to the same property of the initially painted squares.

Share this post


Link to post
Share on other sites
  • 0
Guest
Kudos to the effort put into this proof. B))

I think what's been said shows that the paintable area lies within

the smallest rectangle that contains the initially painted squares.

OK - that's not a spoiler, since I think everyone who's posted has

said it, or at least realized it.

Now. How does a consequence of that fact get to the proof?

Relate a fundamental property of that rectangle to the same property of the initially painted squares.

What exacly do you want to know?

I dont think im even close here, but Im not sure what you exactly want me to find a proof/link between.

The area covered by the paint is contained in the smallest possible rectangle in which there is a "initally painted" in either diagonals from others, or ( in the same row (with up to 1 space in between) and in the same column( whith up to 1 space in between)).

Share this post


Link to post
Share on other sites
  • 0
Guest

One thing becomes clear - the initially painted squares MUST be on a diagnol in order for the magic paint to fill in more than just one "round" of squares after the initial group.

Share this post


Link to post
Share on other sites
  • 0
Guest
One thing becomes clear - the initially painted squares MUST be on a diagnol in order for the magic paint to fill in more than just one "round" of squares after the initial group.

No they dont..

X . X . .

. . . . .

. . X . X

. . . . .

. . . . X

. . X . .

. . . . .

X . X . X

. . . . .

. . X . .

both these fill a 5x5 with only 5 squares, not in a diagonal formation

didn't turn out properly!

Edited by bonanova
Fixed the spacing using courier font

Share this post


Link to post
Share on other sites
  • 0
What exacly do you want to know?

I dont think im even close here, but Im not sure what you exactly want me to find a proof/link between.

The area covered by the paint is contained in the smallest possible rectangle in which there is a "initally painted" in either diagonals from others, or ( in the same row (with up to 1 space in between) and in the same column( whith up to 1 space in between)).

Yes, but what does it take to completely paint that rectangle?

e.g., starting with the four corners encompasses, but does not paint, the entire square.

Shall I give a clue?

Share this post


Link to post
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...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...