# Checkerboard City versus the ACDWNPP

The Association for the Construction, Development and Wellbeing of Nuclear Power Plants (or simply ACDWNPP for short) plans to build a new nuclear power plant in Checkerboard City. As you all surely know, the area of Checkerboard City is divided into 144 square blocks that are arranged in the form of a 12x12 checkerboard. For building the power plant, the ACDWNPP needs to purchase 12 of these blocks that form a 3x4 or 4x3 rectangular region.

The town council of Checkerboard City wants to protect Checkerboard City against this nuclear threat. The council decides to purchase a small number of blocks so that there remains no possibility for the ACDWNPP to get a 3x4 or 4x3 rectangular region (from the remaining blocks).

Question:
What is the smallest possible number of blocks that the town council needs to purchase?

The city council needs to purchase

12 blocks.

Note that, we can divide the $12 \times 12$ board into 12, $3\times 4$ region. Each of these regions needs a block, otherwise the ACDWNPP can buy that region. So, we need at least 12 blocks.

A solution with 12 blocks is given below.

Here's a solution requiring 13 blocks; I doubt that it's optimal. I'm sure there's a nice mathematical solution to the problem, but I haven't figured it out.