Minimal Possible Number

Suppose that the centres of unit squares have coordinates $(i,j)$ , where $i=1,2, \dots , 99$ ; $j=1,2, \dots , 99$ . The unit square with centre at $(i,j)$ will be denoted by $u(i,j)$ . Let the marked unit squares be:

• $u(5k,5l+1)$ , where $1 \le k \le 19,0 \le 19$ , and
• $u(m,5n)$ , where $1 \le m \le 99,1 \le n \le 19$ .

Then it can be seen that the total number of marked unit squares is 2261, and any sub-square $5 \times 5$ has exactly $6$ marked unit squares.

Let $k$ be a positive integer. By the method of mathematical induction, we can see if any $5 \times 5$ sub-square of the grid $(5k+4) \times (5k+4)$ has at least $6$ marked unit squares, then the total number of marked unit squares is at least $6k^2 + 5k$ .

• $k=1\cdot 6 \cdot 1^2 + 5 \cdot 1 = 11$ . Consider two $5 \times 5$ squares: the square consisting all $u(k,l)$ , where $1 \le k \le 5,1 \le l \le 5$ and the square consisting all $u(k,l)$ , where $5 \le k \le 9,5 \le l \le 9$ . Each of these $5 \times 5$ squares contains at least 6 marked unit squares and their intersection is the unit square $u(5,5)$ .

Therefore the total number of marked unit squares is at least $11$ .

• Suppose the statement is correct for a $(5k+4) \times (5k+4)$ grid $A$ and consider a $(5k+9) \times (5k+9$ ) grid $B$ . Suppose that $A$ consists of all unit squares $u(i,j)$ , where $1 \le i \le 5k+4,1 \le j \le 5k+4$ and $B$ consisting of all unit squares $u(i,j)$ , where $1 \le i \le 5k+9,1 \le j \le 5k+9$ .

Let $5 \times 5$ squares $U_s, s=1,2, \dots , k+1;$ consist of all unit squares $u(i,j)$ , where $5k+5 \le i \le 5k+9,5s - 4 \le j \le 5s$ and $5 \times 5$ squares $V_t, t=1,2,\dots , k+1;$ consist of all unit squares $u(i,j)$ , where $5t-4 \le i \le 5t,5k+5 \le j \le 5k+9$ . Note that the squares of $U_{k+1}$ and $V_{k+1}$ share a unit square $u(5k+5, 5k+5)$ , all other pairs of $U_s$ and $V_t$ squares do not share any unit square. Therefore, since the union of $k+1$ $U_s$ and $k+1$ $V_t$ squares is a subset of the set $B-A$ , the set $B-A$ contains at least $6 \cdot 2(k+1)-1=12k+11$ marked squares. Thus, by inductive hypothesis, $B$ contains at least $6k^2 + 5k + 12k+11 = 6(k+1)^2 + 5(k+1)$ . Done.

At $k=19$ , we get that the grid $99 \times 99$ contains at least $\boxed{2261}$ marked unit squares. Whew! :P