Some squares of the $2013$ x $2013$ board are shaded so that any $19$ x $19$ block of squares has at least $21$ shaded squares. At least how many squares of the board are shaded?

Im pretty sure you’re supposed to arrange the shaded squares into diagonals with a distance of 18 squares between them because then every $19$ x $19$ square will have exactly 21 squares and with this method you will get $225123$ shaded squares or $\frac{111*2010}{2}*2+2013$ enter image description here

enter image description here

But I don’t know how to prove this is the most efficient because I know that placing shaded squares closer towards the centre are better because they are present in more $19$ x $19$ squares

Suggestions and solutions would be appreciated

  • $\begingroup$ Just to make sure, which contest is this from? Is the contest ongoing? $\endgroup$ – Toby Mak Nov 8 at 13:13
  • 1
    $\begingroup$ @TobyMak - the likelihood is that the contest was in 2013 $\endgroup$ – Henry Nov 8 at 13:25
  • 1
    $\begingroup$ I think the optimal solution probably looks something like what you drew but your numbers are off. 2013/19 is a little more than 105. Hence I can cover the big square with $105^2$ blocks that are fully disjoint. Each of these blocks must contain at least 21 black squares, so there are at least $105^2*21=231525$ black squares in any valid configuration. $\endgroup$ – quarague Nov 8 at 13:49
  • $\begingroup$ @TobyMak its from a training competition in 2013 not the competition itself $\endgroup$ – Tyrone Nov 8 at 14:24
  • 2
    $\begingroup$ Your method doesn’t put 21 black squares in each 19x19, your top picture is of a 20x20. If you cover the plane with identical backwards Ls at the bottom right hand corners of 19x19 squares, you can get to 2100 above quaragues limit of 231525, doing it in 233,625 $\endgroup$ – Robo300 Nov 8 at 16:45

Your Answer

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

Browse other questions tagged or ask your own question.