wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Disappearing Black Squares
        
(Message started by: william wu on Dec 11^th, 2007, 10:30am)

Title: Disappearing Black Squares
Post by william wu on Dec 11^th, 2007, 10:30am

Consider an infinite square grid in which a finite number of squares are colored black, and the rest of the squares are white. We construct a new square grid according to the following rule: a square is black if and only if at least three of its four neighbors were black in the previous stage. If this process is repeated indefinitely, prove that eventually there are no black squares left.

Title: Re: Disappearing Black Squares
Post by towr on Dec 11^th, 2007, 10:56am

[hide]It seems to me the bounding box the black squares can be in decreases in size from the outside in by two rows and two columns each step, until it's gone[/hide]

Title: Re: Disappearing Black Squares
Post by SMQ on Dec 11^th, 2007, 11:17am

Not quite, towr -- [hide]at least not for a bounding box orthogonal to the grid. The edge of a solid rectangle is stable, it is only the corners which are eroded. However, if we consider a diagonal bounding box, rotated 45-degrees to grid, your observation holds, as every black square on the diagonal bound has at most two neighbors and so will be white in the next iteration
[/hide]
--SMQ

Title: Re: Disappearing Black Squares
Post by Hippo on Dec 11^th, 2007, 2:11pm

on 12/11/07 at 11:17:03, SMQ wrote:

[hide] However, if we consider a diagonal bounding box, rotated 45-degrees to grid, your observation holds, as every black square on the diagonal bound has at most two neighbors and so will be white in the next iteration
[/hide]
--SMQ

Nice proof ;)

Title: Re: Disappearing Black Squares
Post by temporary on Jan 23^rd, 2008, 6:28pm

[hide]Since there are infinite white squares, there are no black squares(there are, but they would be 0% of the board.[/hide] Srn347 would have thoroughly enjoyed answering an infinity based riddle like this.

Title: Re: Disappearing Black Squares
Post by towr on Jan 24^th, 2008, 12:48am

on 01/23/08 at 18:28:43, temporary wrote:

And you're just as wrong as he used to be..

Title: Re: Disappearing Black Squares
Post by Hippo on Jan 24^th, 2008, 5:23am

I have thought about temporary ... is he srn347 or not. And now, he is citing him ... at least he have not attacked us so far ;)
Oh, he made its own thread srn347 sm347 ... so I am not first with this impression.

Title: Re: Disappearing Black Squares
Post by rmsgrey on Jan 24^th, 2008, 8:30am

on 01/23/08 at 18:28:43, temporary wrote:

Consider a finite grid instead, formed by taking the original infinite grid, and, for each black square, identifying the 21*21 square with that black square at its centre. Take the union of all those 21*21 pieces, and, for each connected component, take the minimal orthogonal bounding rectangle. This may cause some previously disconnected components to become connected, so take bounding rectangles recursively until each connected component is an orthogonal rectangle. Discard the rest of the original grid, and iterate on the new, finite grid (it must be finite because each of the finite number of steps added a finite area to the grid). So long as none of the border cells turn black, the finite grid will behave the same way as that portion of the infinite grid.

Title: Re: Disappearing Black Squares
Post by ThudanBlunder on Jan 24^th, 2008, 1:08pm

on 01/24/08 at 05:23:33, Hippo wrote:

I have thought about temporary ... is he srn347 or not.

He uses uncharacteristic words such as 'thoroughly' and 'ordinariness'. But surely an imposter would not make so many posts. Anyway, he should stay away from Putnam and confine himself to Easy, What Happened? and Why Am I a Snotty-nosed Little Dweeb?

Title: Re: Disappearing Black Squares
Post by temporary on Jan 24^th, 2008, 10:45pm

Is your rudeness an imitation of strength or intellect? More importantly, how was my answer wrong? x/infinity=0. Otherwise, how would the squares just disappear? Are the three of four neighbors counted vertical/horizontal, because I counted diagonal?

Title: Re: Disappearing Black Squares
Post by towr on Jan 25^th, 2008, 12:29am

on 01/24/08 at 22:45:07, temporary wrote:

More importantly, how was my answer wrong? x/infinity=0.

Considering infinity isn't a real number you can't divide by it.

Quote:

Otherwise, how would the squares just disappear?

Because there is a process going on that changes the number of black squares in each step. It doesn't matter if the board is infinite or not, as rmsgrey has shown.

Title: Re: Disappearing Black Squares
Post by temporary on Jan 25^th, 2008, 6:59am

on 01/25/08 at 00:29:55, towr wrote:

Considering infinity isn't a real number you can't divide by it.

Because there is a process going on that changes the number of black squares in each step. It doesn't matter if the board is infinite or not, as rmsgrey has shown.

Infinity is hyperreal. And if the squares dissappear, it must be a paradox since logically they couldn't all be gone.

Title: Re: Disappearing Black Squares
Post by towr on Jan 25^th, 2008, 7:40am

on 01/25/08 at 06:59:36, temporary wrote:

Infinity is hyperreal.

But we're not dealing with hyperreals.

Quote:

And if the squares dissappear, it must be a paradox since logically they couldn't all be gone.

That clearly demonstrates you don't understand the problem; at all.
If you have 1 single square, then by the rules described in the opening post, in the next iteration it will be gone. There is no mystery or paradox as to why it's gone; it is stated in the rules that if it doesn't have at least 3 neighbours it won't be on the plane in the next iteration.
Look up cellular automata, or conway's game of life.

And you can consider yourself ignored from now on. Regardless of whether or not you're srn347, you're just as obtuse, annoying and willfully ignorant; and I've had enough. Goodbye, and I hope you grow out of.

Title: Re: Disappearing Black Squares
Post by Icarus on Jan 25^th, 2008, 5:15pm

on 01/25/08 at 06:59:36, temporary wrote:

Infinity is hyperreal.

And if you bring in the hyperreals, x/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0 either.

But in any case, probabilities and percentages are calculated using real numbers, not hyperreals, and 0% is not the same as none existing when infinite amounts are involved.

Title: Re: Disappearing Black Squares
Post by temporary on Jan 25^th, 2008, 5:53pm

Ok. How would the second board have no black squares though? Perhaps infinitely small black squares.

Title: Re: Disappearing Black Squares
Post by Icarus on Jan 25^th, 2008, 5:58pm

??? Have you read the riddle? At each step, any black square that doesn't have 3 black neighbors (of 4 neighbors total, so diagonals are not considered neighbors) are removed. As rmsgrey has shown, eventually, this removes all the black squares.

Title: Re: Disappearing Black Squares
Post by temporary on Jan 25^th, 2008, 8:21pm

Oh, you keep repeating it. I thought it was only done once. If repeated indefinitely of coarse they will disappear. That is why they must be finite. If it was diagonal, it would have the same answer.

Title: Re: Disappearing Black Squares
Post by rmsgrey on Jan 26^th, 2008, 10:01am

on 01/25/08 at 17:58:18, Icarus wrote:

As rmsgrey has shown, eventually, this removes all the black squares.

Thanks for the credit, but all I've shown is that you can reduce it to a finite problem, the solution of which also solves the infinite case.

SMQ got there first with the solution to the infinite case.

Title: Re: Disappearing Black Squares
Post by Icarus on Jan 26^th, 2008, 10:08am

My apologies for the mis-attribution. I should have checked more carefully.