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

[Prime]

Here is a proof (semi-formal) that you can not paint 8x8 board with less than 8 initially magic painted squares.

Few propositions to start:

1. Any contiguous painted shape will continue to paint itself until it forms a proper rectangle. (Non-proper rectangle will have concaved corners, which will cause their neighboring square to be painted.

2. Proper rectangle will stop painting. (That’s an obvious point. However, formal proof does not avail itself to me that late at night.)

3. A rectangle can not extend beyond the boundaries set by initially painted squares. (Suppose you painted several squares. Regard the one furthest to the north. It’s northern neighbor may only be painted by aid with another square, which would reside north of our northernmost painted square. Hope, it’s not too convoluted.)

Let’s define a step as a step from one square to another in a straight (rook-like) motion – not diagonally. (Two diagonally neighboring squares are two steps away from each other). Then two squares automatically paint if and only if they are two steps away.

Now select any square on the board, and you’ll see that from it you need 7 steps to connect north-south and east-west borders. Thus must have 14 steps from any square to reach the four boundaries. As I stated earlier two squares must be situated 2 steps away to effect auto-paint. That makes it 14/2 = 7 ==> minimum squares to paint in order to reach all boundaries from initially selected square.

There are many methods to paint the board with the minimum of 8 initially painted squares, as long as there is no redundancy. I.e. no initially painted square falls within the boundaries of other initially painted squares in any of the four directions.

Long diagonal is one example. Another way: a1, c1, e1, g1, h2, h4, h6, and h8.

Academically inclined logician may find that proof incomplete, but I think it’s convincing enough.

[Prime]

And here is a simple procedure for choosing a set of 8 hand-painted squares which will paint the entire board:

1. Select any square on the board.

2. Select second square exactly two steps away. (See the definition of step in my previous post).

3. Draw the resulting rectangle using the outer boundaries of defined by selected squares.

4. Select another square exactly two steps away from the rectangle (drawn in step 3).

5. Repeat step 3 and 4 until you have selected 8 squares.

For example, using that algorithm you may choose squares as following:

c1, c3, b4, a5, e4, g5, h6, and h8.

I believe you can not create a situation where you would not be able to paint the entire board with 8 hand-painted squares using that algorithm. I can't think of a formal proof yet. That's a new puzzle.

[Prime]

...

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

I'm not so sure about that... Inductive proofs are treaturous and often fallacious. If you want to reuse NxN painted square in prooving your case for (N+1)x(N+1), consider following example.

There are but two minimal ways to paint 2x2 square -- use one diagonal, or the other. There are 4 different ways to enclose already painted 2x2 square into a 3x3 one. Thereafter, you can paint just one square in the empty corner of 3x3 and the 3x3 gets painted entirely. HOWEVER, aside from those 8 variations, there are other possibilities. Paint in any 3 corners of 3x3 square and it gets painted from head to toe. THEREFORE, how can you apply inductive proof if minimal painting of N+1 square does not need to rely on painting of any of its subsquares of size N?

[Prime]

And here is a next level puzzle that occurred to me:

Suppose that you have 8 blobs of magic paint and you throw them at the board using your random paint sprayer. The random paint sprayer guarantees that each blob will paint exactly one different square on the board. What’s the probability that the board will get painted completely?

[Prime]

I must not attempt proofs after midnight. My proof in post #27 suffers from the very flaw, I warned about. It picks a certain method of selecting squares that would paint an entire board. However, that method does derive all possible variations.

Here is an inductive/recursive proof that Bona, probably, had in mind:

Two painted rectangles may be arranged as following to make another larger painted rectangle:

These two arrangements (and all their symmetries) are maximal in a way they ensure the largest perimeter of the resulting rectangle. The sides of the rectangle resulting from the two overlapping rectangles are: (x1 + x2 + 1) and (y1 + y2 – 1), while the sides of the rectangle resulting from two corner-touching ones are (x1 + x2) and (y1 + y2). In both cases the perimeter of the resulting rectangle equals sum of the perimeters of two smaller rectangles. No other arrangement can produce larger perimeter, nor area.

There is a minimal painted rectangle – that of size 1, where number of painted squares must be at least 1/4 of the perimeter length. (There are 4 sides with one painted square.)

Suppose there are 2 rectangles, which are arranged in way to create a new larger painted rectangle in accordance with magic paint properties. The number of hand-painted squares in the resulting rectangle will be equal to sum of hand-painted squares of the two smaller ones. (We did not add, or subtract any hand-painted squares.) The perimeter of the larger rectangle will also be equal to sum of the smaller rectangles at the most. Thus the new rectangle will retain the property of at least 1/4 of the perimeter hand-painted squares of its “creators”.

Since we always must start building larger rectangles from single hand-painted squares, no auto-painted rectangle can escape inheriting that property of at 1/4 of the perimeter number of hand-painted square.

QED

Here is an interesting set of hand-painted squares which will paint the entire board. Yet it cannot be derived using my algorithm from post #28.

Another correction: there are not 8 variations (as I said in post #29), where 3x3 square could be constructed from 2x2 one, but only 6. And there are total of 14 variations to choose 3 squares which would paint a 3x3 board.

My puzzle stands: How many different sets of 8 hand-painted squares, which would paint the entire board are there?

Edited August 8, 2008 by Prime

[bonanova]

Prime has it.

1. When cells become painted, the total perimeter of the painted area does not increase, so the perimeter of the painted area never exceeds the total perimeter of the original painted cells.
   
2. The perimeter of an NxN square is 4N.
   
3. The total perimeter of N cells which have no common sides is 4N.
   
4. Therefore an NxN square cannot be painted by fewer than N initially painted cells.
   

[Prime]

Prime has it.

1. When cells become painted, the total perimeter of the painted area does not increase, so the perimeter of the painted area never exceeds the total perimeter of the original painted cells.
   
2. The perimeter of an NxN square is 4N.
   
3. The total perimeter of N cells which have no common sides is 4N.
   
4. Therefore an NxN square cannot be painted by fewer than N initially painted cells.
   

Some people may ask you for a proof of your proposition (1). To clarify, you mean that each newly painted square removes two borders from the outside perimeter, while it can add at the most two of its remaining borders to the newly formed perimeter.

Edited August 8, 2008 by Prime

[bonanova]

Some people may ask you for a proof of your proposition (1). To clarify, you mean that each newly painted square removes two borders from the outside perimeter, while it can add at the most two of its remaining borders to the newly formed perimeter.

Yeah. I thought you'd already shown statement 1, so I just restated it. Here's the proof.

1. If the cell to be painted shares two edges with painted cells, painting it removes two units of perimeter and adds two units - the perimeter remains the same.
   
2. If the cell to be painted shares three edges with painted cells, painting it removes three units of perimeter and adds one unit - the perimeter decreases.
   
3. If the cell to be painted is surrounded on four sides with painted cells, painting it removes four units of perimeter and adds none - the perimeter decreases.
   
4. These are the only cases.
   

Therefore, when a cell becomes painted by other cells, the perimeter of the painted region does not increase.

[bonanova]

My puzzle stands: How many different sets of 8 hand-painted squares, which would paint the entire board are there?

I'll start it off

2x2: 2 Sets of initial cells

X_ [2]
_X

3x3: 6 sets of initial cells

X__ [2] X__ [4]
_X __X
__X _X_

4x4: 22 sets of initial cells

X___ [2] _X__ [2] X___ [4] X___ [4] X___ [4] X___ [2] X___ [4]
_X__ X___ ___X _X__ ___X __X_ __X_
__X_ ___X __X_ ___X _X__ _X__ ___X
___X __X_ _X__ __X_ __X_ ___X _X__

5x5:

6x6:

7x7:

8x8:

Numbers in parentheses are the number of 90-degree rotations that produce different patterns.

[Prime]

If we have this discussion in the open, can someone borrow our findings and make them a subject of their PhD thesis in Math or Computer Science? Would we feel cheated?

I don’t quite follow Bona’s "__X" notation. At any rate, (N+1)x(N+1) square does not have to be based on ay NxN square. I see 14 variations – not 6, to paint 3x3 board with 3 hand-painted squares. Here is an illustration:

The diagonal path provides only two variations, the other 3 paths – 4 variations each. (Use 90-degree rotation.) The two paths at the top could be based on 2x2 painted board, the other two paths – could not.

First, I thought my variation on this puzzle could be solved by determining the order of the algorithm that I suggested (post #28). However, that algorithm can not produce all possible combinations (see illustration, post #31).

Suppose, we have devised an algorithm that produces all possible combinations of 8 hand-painted squares, which we seek. Then we’d have to determine, how many duplicate solutions it produced. And figuring out the order of algorithm (how many solutions it produced) could be non-trivial task too.

Bona already noted 90-degree rotational symmetry (post #35). Symmetry could play an important role in solving the problem. I’d also like to point out mirror symmetry. Regard b1 square. It has rotational symmetries: (b1, a7, g8, h2) and those have mirror symmetries: (b8, h7, g1, a2). Logically, those squares are similar.

If you followed, what I have written here, you may be able to deduce that I am pretty much clueless with respect to the solution of my own puzzle. However, I can figure the upper boundary: the answer is less than combinations of 8 from 64.

[bonanova]

I don’t quite follow Bona’s "__X" notation.

X denotes initial cells.

I missed one of your 3x3 configurations [lower left]; your other [lower right] doesn't paint.

Including the 3x3 ones I missed, and using "o" instead of "_" for unpainted squares:

2x2: 2 Sets 


  Xo [2]

  oX


3x3: 14 sets 


  Xoo [2]   Xoo [4]   [color="#8B0000"]Xoo [4]   oXo [4][/color]

  oXo       ooX       [color="#8B0000"]ooo       ooo[/color]

  ooX       oXo       [color="#8B0000"]XoX       XoX[/color]


4x4: 54 sets - probably missed some


  Xooo [2]   oXoo [2]   Xooo [4]   Xooo [4]    Xooo  [4]  Xooo [2]    Xooo [4]

  oXoo       Xooo       oooX       oXoo        oooX       ooXo        ooXo

  ooXo       oooX       ooXo       oooX        oXoo       oXoo        oooX

  oooX       ooXo       oXoo       ooXo        ooXo       oooX        oXoo


  [color="#8B0000"]Xooo [4]   Xooo [4]   Xooo [4]   Xooo [4]   Xooo [4]   Xooo [4]   Xooo [4]   Xooo [4][/color]

  [color="#8B0000"]oXoo       oXoX       oXoX       oooX       ooXo       oXoo       oXoX       oooX[/color]

  [color="#8B0000"]oooo       oooo       oooo       oooo       oooo       oooX       oooo       oXoo[/color]

  [color="#8B0000"]oXoX       oXoo       oooX       oXoX       oXoX       oXoo       ooXo       oooX[/color]

[/codebox]

[Prime]

Oh, I got the notation. It’s an illustration without using “Paintbrush”. To simplify we could represent each row of a rectangle as a binary number with one in the position of each painted square and zero otherwise. Then list set of resulting numbers starting from top row. For example: one painted diagonal variation of the 3x3 square could be represented as (100, 010, 001); or if you convert it into hexadecimal: (4,2,1).

I don’t think it is feasible to solve this problem by trying to traverse all possibilities by hand. (I already tried solving “Dr. P, S, and N problem on this forum without use of a computer, and just got a headache.)

Combinations of 8 from 64 are over 4.4 billion – a respectable number.

The algorithm could be:

1. Find all possible ways to break down a rectangle into two other rectangles that would paint the entire area with the minimum number of initial squares.

2. Repeat (1) for each rectangle found.

But that would be a programming heuristic solution.

More elegant way would be finding how some common property of each and every configuration of initial squares limits the number of such configurations.

[Guest]

To get us started and bring up some important characteristics that may aid in a final probability for N random blobs filling an NxN square, I present

Some observations which I believe are correct:

1. There must be a blob in each of the edge rows of the square. Note that a blob in a corner counts for both edges.
   
2. There can be NO instances where two blobs touch each other, as this would preclude a NxN square (see previous proofs showing that the perimeter of all starting blobs must be equal to 4N to complete the NxN square)
   
3. There must not be any two consecutive rows or columns that are entirely blank.
   

Also, I present

A method of thinking of blobs and covered rectangles in a more general term:

I call this "Clueless's Expanding Rectangle".

1. Any rectangle and/or blob may be considered to be a rectangle like so: ( min x, min y, max x, max y ) or shorthand (x,y,X,Y). For a blob x = X and y = Y.
   
2. Rectangles and/or blobs may be combined when there are 2 or less "steps" between them. For any particular combination of rectangles and blobs this can be tested by 4 cases in which you extend two adjacent sides and test for intersection with the opposite corner of the target (e.g. X1 + 1 >= x2 && Y1 + 1 >= y2) and 4 cases where you extend one side twice and test for intersection with both relevant corners of the target (e.g. X1 + 2 >= x2 && [y1 <= Y2 || Y1 >= y2]). Ignore the programming pseudocode if you don't understand it.
   
3. Once combined, the rectangle now consists of ( min(x1,x2), min(y1,y2), max(X1,X2), max(Y1,Y2) ) and all squares inside of this new larger rectangle can be filled.
   
4. If after combining all blobs and rectangles there is only one rectangle that looks like (1,1,N,N) then you are done.
   

Finally, I present one hypothesis:

If all the above observations are shown to be true, the board is solvable even without solving by a method such as the expanding rectangle. I cannot think of a counterexample, but if you can, it would be good to know before I try to come up with an equation for the probability.

I hope this helps, and if you see anything that looks incorrect, please mention it.

[Prime]

If the three conditions, Clue set forth, are NOT met, the board will not autopaint entirely. However, meeting those conditions does not guarantee filling the board:

Note, each and every column and row on that board has a square, no two painted squares touch with their sides. But no auto-paint.

The probability question, is really the question of how many different collections of 8 initially painted squares will autopaint the entire board. The total number of combinations of 8 from 64 is 4,426,165,368.

[brainz]

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?

what about painting 4 squares in the center

[Prime]

Bona,

Your 54 combinations to fill 4x4, are missing some variations, some are incorrect, and, possibly, some are counted more than once. (I did not check close enough to be sure.)

The last combination you showed (1000,0001,0100,0001), will not paint. Also, consider

0100

1001

0000

0010

or (4,9,0,2) in hexadecimal. This one has 4 90-degree roatational variations, then a mirror image and four rotational variations of that -- 8 more variations in all.

Another one I don't see in your set: (2,4,8,1) with 4 rotations.

A method for traversing all possible variations while keeping track of all duplicate solutions at the same time -- would be an algorithm to find the answer. The challenge in that approach is to design an algorithm that would only go through those variations that satisfy the condition of painting the board. And, of course, keeping track of duplicate solutions. Then a computer program could come up with solution.

Although, I still think there might be some analytical way. Perhaps, binary representation of the position on the board could be used somehow? Or rotations of the board?

[Guest]

For purely brute forcing a solution, it may be helpful to note that any possible configuration can be stored in its entirety in an unsigned 8-byte integer (commonly called a double or real) where each byte corresponds to a row, and each bit corresponds to a column.

Edited August 11, 2008 by itsclueless

[bonanova]

Bona,

Your 54 combinations to fill 4x4, are missing some variations, some are incorrect, and, possibly, some are counted more than once. (I did not check close enough to be sure.)

The last combination you showed (1000,0001,0100,0001), will not paint. Also, consider

0100

1001

0000

0010

or (4,9,0,2) in hexadecimal. This one has 4 90-degree roatational variations, then a mirror image and four rotational variations of that -- 8 more variations in all.

Another one I don't see in your set: (2,4,8,1) with 4 rotations.

A method for traversing all possible variations while keeping track of all duplicate solutions at the same time -- would be an algorithm to find the answer. The challenge in that approach is to design an algorithm that would only go through those variations that satisfy the condition of painting the board. And, of course, keeping track of duplicate solutions. Then a computer program could come up with solution.

Although, I still think there might be some analytical way. Perhaps, binary representation of the position on the board could be used somehow? Or rotations of the board?

I'm sure you're right that I've missed some.

But just to satisfy my curiosity, you say - (1000,0001,0100,0001), will not paint.

Doesn't it paint, like this?

(1000,0001,0101,0001)

(1000,0001,0111,0001)

(1000,0011,0111,0011)

(1000,0111,0111,0111)

(1100,1111,0111,0111)

(1110,1111,1111,0111)

(1111,1111,1111,1111)

[Prime]

I'm sure you're right that I've missed some.

But just to satisfy my curiosity, you say - (1000,0001,0100,0001), will not paint.

Doesn't it paint, like this?

(1000,0001,0101,0001)

(1000,0001,0111,0001)

(1000,0011,0111,0011)

(1000,0111,0111,0111)

(1100,1111,0111,0111)

(1110,1111,1111,0111)

(1111,1111,1111,1111)

You are right. I didn't notice 0001 in the second and 4th row would start painting.

I like your representation of how that combination would paint -- each next line obtained from previous by one or more boolean AND operations. That's a step toward formalization of painting process.

Here are 6 patterns that could be constracted with intial 4 squares and paint entire 4x4 area. They have different number of distinct rotational and mirror symmetries. Some will produce different number of duplicate solutions. E.g., pattern 1 and 2 could be derived from the same painted diagonal. But you can cover all possible combinations with 2 rectangular shapes. In other words, there are no 3 rectangles that would paint the entire board, which you wouldn't be able to represent as just 2 rectangles.

[Prime]

Oops! Configurations 5 and 6 in my illustration above are one and the same.