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

  • 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?2011-10-21
  • 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$.2011-10-21
  • 1
    awesom-o: a proof of the claimed exact values?2011-10-21
  • 0
    @Didier Youre right I'm not sure how one would prove it, but they are obtained trivially by stacking a 3x3 square with some squares removed next to eachother.2011-10-21
  • 0
    awesom-o: hence these are **lower bounds**, right?2011-10-21
  • 0
    @awesome-o $r_4$ can be improved to $\geq \frac{9}{16}.$2011-10-22
  • 4
    I found a reference which settles all but $r_4$ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2372011-10-22
  • 1
    @awesom-o: Care to explain the paper and post the explanation here as an answer to your question?2011-10-23
  • 0
    @Didier No, not really. Read the paper.2011-10-23
  • 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.)2011-10-23
  • 0
    I have just run into this post today. I see the paper of Elkies... I wish I knew about it in 2003 or so. I wrote a paper that appeared in the Monthly in 2008 ([arXiv:math/0608140](http://arxiv.org/abs/math/0608140)) and there are related questions in [arXiv:1201.4624](http://arxiv.org/abs/1201.4624). I'm interested in a proof for the case $r_4=3/5$. There are similar conjectures for semi-regular tessellations type graphs.2012-04-07
  • 0
    @user28520: Welcome to the site. I have converted your answer to a comment. Please note that answers should be reserved for 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.stackexchange.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$.