Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If every square of the unit square lattice in the plane is colored black or white according to a set of rules, is there a way to find the maximum asymptotic ratio $r_n$ of the number of black squares to the total number of squares?

If the rules are that each black square can have at most $n$ adjacent (side-by-side or corner-to-corner) black squares, here are some partial results for every possible $n$: $$ r_0=\frac{1}{4},\quad r_1=\frac{1}{3},\quad r_2=\frac{1}{2},\quad r_3=\frac{1}{2},\quad r_4\geq\frac{3}{5},\quad r_5=\frac{9}{13},\quad r_6=\frac{4}{5},\quad r_7=\frac{8}{9},\quad r_8=1 $$

share|improve this question
1  
What do you mean by "reached"? "Reached" in the sense of getting there from somewhere else (the origin?), or "reached" in the sense of "attained"? And how do you define the ratio of infinite numbers of squares? –  joriki Oct 21 '11 at 5:15
1  
With $r_k$ the asymptotic ratio of the number of black squares to the total number of squares, $r_1\geqslant\frac13$, $r_2\geqslant\frac12$ and $r_5\geqslant\frac23$. –  Did Oct 21 '11 at 6:19
1  
awesom-o: a proof of the claimed exact values? –  Did Oct 21 '11 at 16:09
4  
I found a reference which settles all but $r_4$ citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.237 –  awesom-o Oct 22 '11 at 5:13
2  
@awesom-o: No thanks, I will not (read the paper). Why should I? (You seem to have the strangest conception of the way the site works--and of politeness, by the way.) –  Did Oct 23 '11 at 13:06
show 7 more comments

2 Answers 2

up vote 4 down vote accepted

You can do $r_4$ with a $\frac{3}{5}$ ratio

. . X X X . . X X X
X X . . X X X . . X
. X X X . . X X X .
X . . X X X . . X X
X X X . . X X X . .
. . X X X . . X X X
X X . . X X X . . X
. X X X . . X X X .
X . . X X X . . X X
X X X . . X X X . .

This is an answer so that I can write the ascii art.

share|improve this answer
add comment

You may be able to get more bounds (upper and/or lower) by looking at this as a coloring of a graph and by thinking about how the relative proportions of black-black, black-white, and white-white edges relate to the proportions of black and white vertices. The proportion of black vertices $p_b$ should be $p_{bb} + \frac{1}{2} p_{bw}$.

For $r_7$ each black vertex must be adjacent to at most $7$ black vertices, so each black vertex must be adjacent to at least one white vertex, so each black vertex must be associated with at least one black-white edge. If every other edge is black-black then $\frac{7}{9}$ of the edges are black-black and $\frac{2}{9}$ of the edges are black-white, so the upper bound on the proportion of black vertices would be $\frac{7}{9} + \frac{1}{2} \cdot \frac{2}{9} = \frac{8}{9}.$ Therefore $\frac{8}{9}$ is both an upper and lower bound on $r_7$. Maybe a similar approach could give upper $r_k$ bounds for more interesting $k$.

Edit: this answer is not so useful now that we have found a paper that gives exact values for all $k$ except $k=4$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.