6
$\begingroup$

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 $

  • 0
    @user28520: Welcome to the site. I have converted your answer to a comment. Please note that answers should be reserved $f$or posts that answer the question. But because you do not have 50 reputation points yet, [you can only comment on your own questions and answers](http://meta.stacke$x$change.com/questions/19756/how-do-comments-work/19757#19757). So, you didn't do anything wrong; the "add comment" button will only appear for you once you gain 50 points. Here is an [explanation of reputation points](http://meta.stackexchange.com/questions/7237/how-does-reputation-work/7238#7238).2012-04-07

2 Answers 2

4

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.

4

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