[bonanova]

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?

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

[Guest]

wouldn't this work?

untitled.bmp

[Guest]

geez guys im gonna have to break out photoshop for this one

[Guest]

wouldn't this work?

untitled.bmp

Nevermind, caught my mistake.

[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:

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

[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 July 31, 2008 by taliesin

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

[Guest]

nvm, i can not do it either

edited for stupidity

Edited July 31, 2008 by finance_it

[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

[HoustonHokie]

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 July 31, 2008 by HoustonHokie

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

[Guest]

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

[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 July 31, 2008 by Frost

[Guest]

Had to try it.

Edit: Thanks Frost!

Edited July 31, 2008 by Alyanna

[bonanova]

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

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?

[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?

[bonanova]

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 i² 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.]
   

[HoustonHokie]

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 x_n,y_m to be painted, two of four other squares have to also be painted:x_n-1,y_m; x_n+1,y_m; x_n,y_m-1; or x_n,y_m+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 P₂,Q₂ is less than N₁,M₁, the two arrays will be independent and you'll never be able to paint the whole array from P₁,Q₁ to N₂,M₂.

[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

[bonanova]

Kudos to the effort put into this proof.

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.

[Guest]

Kudos to the effort put into this proof.

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

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

[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 August 6, 2008 by bonanova
Fixed the spacing using courier font

[Guest]

I stand corrected!

[bonanova]

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?