MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Path connected coloured sets on the squared paper

Colour small squares on the standard squared paper in two colors A, B. Name two small squares with common side as "neighbor". Let every colored set be "path connected": for any two small squares of the color A(resp. B) there is a sequence of color A(resp. B) neighbor squares from one to another. Could you help me to prove that must there exists square $3\times 3$ which has 6 squares of same color?

(It is clear that there is infinite path of each color... I constructed a lot of finite examples without desired square $3\times 3$, but they haven't common structure...)

Question: does this $3\times 3$ square exists? I think, yes, but I can't prove it.

Added: There is a counterexample, two spirals without desired square $3\times 3$.

-
1. I cannot understand the problem. Do the small squares form an n×n grid? What’s wrong with a coloring AAB/ABB/AAB of 3×3 grid? 2. The wording suggests that you know a proof. What is the question? – Tsuyoshi Ito Sep 5 2010 at 20:21
I'm starting to see, two roughly equal spirals... – Will Jagy Sep 5 2010 at 20:33
to Tsuyoshi Ito: The question is about infinite paper, plane with integer grid. – Nikita Kalinin Sep 5 2010 at 20:39
To Will Jagy: do you have a accurate example? To Tsuyoshi Ito: no, I can't prove it. – Nikita Kalinin Sep 5 2010 at 20:46
For example, in this picture,  tilingsearch.org/HTML/data129/F12.html  pretend set A is light green combined with dark green, while set B is red combined with black.  Tsuyoshi Ito is correct. If you know how to prove this, you should say. If you don't, you should still be a little more polite about this, indicate why you think it should be true and ask, you are not giving an examination to your students. – Will Jagy Sep 5 2010 at 20:46
show 8 more comments

I believe that such a 3x3 square does not necessarily exist.

A counterexample would take the form of an infinite still life pattern in the life-like cellular automaton rule B123678/S34 (these rules are chosen so that the only patterns that remain stable are the ones in which the number of live cells in each 3x3 box is 4 or 5). Additionally, both the live and dead cells of the pattern should be connected.

But as the following partial double spiral shows (copy and paste it into Golly to view and test) it's possible to form partial double-spiral patterns that, at least in the center of the pattern, have the desired properties. I don't see any good reason why it shouldn't be possible to continue the spiral infinitely.

x = 31, y = 31, rule = B123678/S34
14b4o$12b3o2b3o$10b3o6b3o$8b3o3b4o3b3o$6b3o3b3o2b3o3b3o$5b2o3b3o6b3o3b 2o$5bo2b3o3b4o3b3o2bo$4b2ob2o3b3o2b3o3b2ob2o$4bo2bo2b3o6b3o2bo2bo$3b2o b2ob2o3b4o3b2ob2ob2o$3bo2bo2bo2b3o2b3o2bo2bo2bo$2b2ob2ob2ob2o6b2ob2ob 2ob2o$2bo2bo2b2obo2b4o2bo2bo2bo2bo$2bo2bo2bo2bob2o2b2ob2ob2ob2ob2o$b2o
b2ob2ob2o2bo2bo2bo2bo2bo2bo$b2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$bo2bo2bo2bo
2bo2bo2bo2bo2bo2bo$2ob2ob2ob2ob2ob2o2bo2bo2bo2bo$o2bo2bo2bo2b2o2bob2ob
2ob2ob2o$2ob2ob2ob2o4b2obo2bo2bo2bo$bo2bo2bo2b6o2bo2bo2bo2bo$b2ob2ob2o 3b2o3b2ob2ob2ob2o$2bo2bo2b3o4b3o2bo2bo2bo$2b2ob2o3b6o3b2ob2ob2o$3bo2b
3o3b2o3b3o2bo2bo$3b2o3b3o4b3o3b2ob2o$4b3o3b6o3b3o2bo$6b3o3b2o3b3o3b2o$
8b3o4b3o3b3o$10b6o3b3o$12b2o3b3o!

Here's a screenshot:

-
 Ok, I added a screenshot. Turns out posting images here is easy: just host the image somewhere, click the image icon when you're editing a post or reply, and fill in the url. – David Eppstein Sep 5 2010 at 21:51 Great! I do not see any reason this cannot work infinitely, either. I would really like to see how to generalize this fuzzy-looking pattern into an infinite pattern. – Tsuyoshi Ito Sep 5 2010 at 21:57 Hm. You changed my belief. But what about some kinds of formal proof? – Nikita Kalinin Sep 5 2010 at 22:00 In lieu of a formal proof, I enlarged the spiral to the point where I think the patterns allowing it to continue infinitely are more obvious. – David Eppstein Sep 5 2010 at 22:20 Works for me. As size gets very large, one loop of a path approximates an octagon, slopes of the "edges" (which are all that changes on increasing the size) are given by a knight's move, $2, \; \frac{1}{2}$ and the like. – Will Jagy Sep 5 2010 at 22:39
show 1 more comment

I think the result is false. Consider a sequence of drawings, one of which I will represent here:

&&&&&&&&&&&&&&&
&  &  &  &  &
&  &  &  &  &
&& && && && &&
&  &  &  &  &
&  &  &  &  &
&& && && && &&
&& && && && &&


This is a coloring of a 9 x 15 region which satisfies the conditions and has no 3x3 square with six unit squares of the same color. (unfortunately, there are some rendering problems as I am not seeing how to control the line spacing.) It should be clear how to extend this for mxn regions in which both m and n are arbitrarily large. Now the idea is to develop a compactness style argument which expresses connectedness of both regions, the lack of a 3x3 subregion with at least 6 squares of one color, and the arbitrary size of the diagram. While I do not have the argument nailed down, I suspect one can use this to show an infinite domain colored in such a way as to preserve all the properties. This (plus other poster's evidence to the contrary) is why I believe the poster's assertion that such a 3x3 square exists that contains at least 6 squares of one color is false.

Gerhard "Ask Me About System Design" Paseman, 2010.09.05

-
 In the comments to the question, the questioner says that the intent is that the paper is the infinite grid ℤ×ℤ. But I think that your example is sufficient to disprove the analogous claim for arbitrary large grids, which is also interesting IMHO. – Tsuyoshi Ito Sep 6 2010 at 0:20

Edit: This argument is wrong, as pointed out in the comments. I'll leave it up as a warning to others.

I am going to respond to the question under the assumption that this is about infinite paper (as mentioned by the original poster in the comments), rather than large finite paper, as I think that makes the proof a bit easier. Write $\mathcal{B}$ for the black region and $\mathcal{W}$ for the white region. If either of the regions is bounded then the result is obvious, as in this case there will be either an all-white or an all-black 3x3 square sufficiently far from the origin. So assume neither region is bounded.

Assuming both regions are unbounded, it must be the case (possibly after switching black and white and maybe also a rotation of the plane by $\pi/2$) that $\mathcal{B}$ contains a two-way infinite path through the origin that contains squares with arbitrarily large $x$-coordinate, and also arbitrarily small $x$-coordinate. Since $\mathcal{W}$ is connected, all white squares must lie to one side of this path; by a reflection we can assume they all lie above the path. Then the region below the path is all black and so contains the square you're looking for.

-
 @...that B contains a two-way infinite path... Why? I think, B contains a one-way infinite path - for example, your suggestion is not true in the spiral-shape colouring.... – Nikita Kalinin Sep 5 2010 at 21:27 I cannot see how this argument applies to the case of infinite spirals (see a comment by Will Jagy). To be concrete, the proof is fine up to (and including): “Since W is connected, all white squares must lie to one side of this path” but I do not get the following part: “by a reflection we can assume they all lie above the path.” How do you define “above the path”? – Tsuyoshi Ito Sep 5 2010 at 21:30 Louigi, you appear to be trying to prove that there exists a monochromatic $3 \times 3$ square, but this is false: make the black squares a simple rectangular spiral (0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (2, -1), (2, -2), (1, -2), (0, -2), (-1, -2), (-2, -2), (-2, -1), (-2, 0), (-2, 1), etc. – JBL Sep 5 2010 at 21:32 Tsuyoshi Ito, you're right, my argument is faulty (and in fact would prove a stronger result which is false -- as the spiral example shows -- so I should have realized). – Louigi Addario-Berry Sep 5 2010 at 21:34