2
$\begingroup$

Given a $1000\times 1000$ board. We can place non-overlapping $2\times 2$ squares on the cells. Two $2\times 2$ squares are said to attack each other if they lie in the same pair of adjacent rows (or columns), and the cells between them are all empty. (In other words, we can move one to the other without hitting other $2\times 2$ squares.) At most how many $2\times 2$ squares can we place so that no two attack each other?

If we start with a $5\times 5$ square, it is not hard to draw four $2\times 2$ squares so that they're "off" from one another, and so no two attack each other. We can divide the original $1000\times 1000 $ board into $5\times 5$ subboards, and use this arrangement, which yields $200^2\times 4 = 160000$ copies of $2\times 2$ squares. Is this the best possible configuration?

$\endgroup$
1
$\begingroup$

The following pattern gives you a density of almost $\frac45$, so almost $\frac{10^6}{5}=200000$ copies. You can get the exact number by careful counting - but I am not completely sure how to easily see that not a single extra square is possible ...

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it possible to show, at least, that no more than $200000$ copies are possible? Seems like we can argue that for each $2\times 2$ square, at least one of the two cells below it must be empty, hence the $4/5$ ratio. But this runs into a problem for $2\times 2$ squares adjacent to the bottom of the board. $\endgroup$ – simmons Nov 3 '14 at 23:58

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.