A fantasy game on the Angels&Demons novel

Question

CONTEXT

Recently, I have been reading the novel "Angels & Demons" by Dan Brown and I was kind of fascinated by the plot. This problem is inspired by the novel.

PROBLEM

Assume that the Vatican is a $2019\times 2019$ square. Cameras are placed at the vertices of unit squares. Each camera can cover four unit squares that shares the vertex, except for the cameras on the edge and at the corner of Vatican, which looks after only 2 and 1 unit squares respectively. Now, to prevent further incidents, Cardinal Mortati insists that the cameras must be placed so that if one camera is stolen, then every unit square of Vatican is still watched.

What is the least number of cameras to be placed so that it satisfy the Cardinal's requirement?

Note: This problem is just for fun and does not infiltrate on the story itself.

Answer 1

Thanks @Calvin Lin for your hint, now I am going to post my answer to this problem.

First, we color the table as follow:

It is clear that every red dot covers one and exactly one black square, and each black square is also covered by exactly 2 red dots. In total, there are $2020\times 1010$ or $2\times 1010^2$ red dots. We may now prove that this is indeed the answer to the problem.

It is easy to prove that with this scheme of placing the cameras then the conditions are satisfied.

It is also clear that the number of black squares is $1010^2$, and since each camera only covers one black square, and we need 2 on each square, the least number of cameras is $2\times10^2$

EDITS

I am thinking of changing 2019 to 2020. I think the scheme still applies, although the proof maybe a little more complicated.

Answer 2

Hint: Consider the squares that are in the (odd row, odd column).

There are $1010 \times 1010$ of them, and one camera can cover at most 1 of them.

Hence, we need at least $ 2 \times 1010^2$ cameras.
There is an obvious simple placement that works (even if we require that there is at most 1 camera on each vertex, since a smart thief will just steal both cameras that are at the same vertex)