5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

enter image description here

$\endgroup$
3
$\begingroup$

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.

enter image description here

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