10
$\begingroup$

Let A be a $2013\times2013$ board with $k$ black squares and containing no $L$ shaped black trominoes(in any rotation) and such that if any white square is dyed black then $A$ contains a black $L$ shaped trominoe. What is the least possible value for $k$?

I'm guessing that its $2013\times671$
where we color every column that is $\equiv 2 \bmod 3$. I have no idea how to prove it the least though

$\endgroup$
  • 1
    $\begingroup$ Presumably, you mean, "... then $A$ contains a black L-shaped tromino." $\endgroup$ – Thomas Andrews Aug 6 '13 at 18:09
  • $\begingroup$ You definitely don't want to color the left column then every third column after that, or the right-most column does match. You wan to color the column second from the left, and every third column after that. $\endgroup$ – Thomas Andrews Aug 6 '13 at 18:16
1
$\begingroup$

Another pattern that works looks like this:

enter image description here

More explicitly; first make black all $2\times2013$ squares in rows 2 and 2012. Next make black all $2\times2007$ squares in columns $2$ and $2012$ that are not adjacent to a black square. Next make black all $2\times2007$ squares in rows $5$ and $2009$ that are not adjacent to a black square. Etcetera.

EDIT: I made a mistake in the calculation. This coloring is not an improvement.

In this way rows $2+3n$ and $2012-3n$ each have a string of $2013-6n$ consecutive black squares for every $n\leq334$. Similarly columns $2+3n$ and $2012-3n$ each have a string of $2013-6(n+1)$ consecutive black squares for every $n\leq334$. This leaves $3$ consecutive black squares in row $1007$. As every black square is in precisely one such string, this covers all black squares. Summing up yields the number $k$ of black squares;

$$k=3+\sum_{n=0}^{334}[2\cdot(2013-6n)+2\cdot(2013-6(n+1))]=1350723.$$

This is the same number as for the coloring described in the question; coloring every third column black, starting with the second.

One approach to determining a lower bound is the following: Every black square is adjacent to at most eight white squares. Every white square is adjacent to at least two black squares. The number of white squares is $2013^2-k$, yielding the inequality $$8k\geq2(2013^2-k),$$ from which it follows that $k\geq810434$. This lower bound can be improved by noting that in many ways adjacencies are lost on black squares being adjacent to eachother. For example:

Every white square is adjacent to at least two adjacent back squares. Both these black squares are therefore adjacent to at most seven white squares. In this way a total of $2(2013^2-k)$ adjacencies are lost, two for each white square, if it were not that some pairs are counted more than once. Every pair of adjacent black squares has at most four white squares adjacent to both, hence every pair of lost adjacencies is counted at most four times, i.e. at least $\tfrac{1}{2}(2013^2-k)$ adjacencies are lost. This yields $$8k-\tfrac{1}{2}(2013^2-k)\geq2(2013^2-k),$$ from which it follows that $k\geq964803$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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