The Minimum Number of Tiles

We divide the set of black squares in two subsets, one with the black squares on a even row and other with the black squares on a odd row. Then we can see that a triminoe can't cover two black squares of the same subset. The greater subset is the one made with the odd rows and it has 1007^2 black squares. We can see making a small example that we can cover all the black squares of the other subset using triminoes that also cover black squares of the greater subset. So the solution is 1007^2 (mod 1000) = 49

First of all let me start by saying that it took me a lot of trial and errorand case checking to solve this problem.

Our goal in this problem is to cover all of the black squares $2013 \times 2013$ chessboard with the minimum number of triminoes.

In the question it states that our black squares are in the corner. It may not seem like an important detail but actually it specifies the actual number of black squares on the board. Let's the image of the $3 \times 3$ chessboard again.

This is a Chessboard

You can see that there is one black square more than the white ones. This true for any $n \times n$ chessboard where $n$ is an odd number and the black squares are on the corner. So, the number of black squares on a $(2m +1) \times (2m +1)$ chessboard is equal to $\lfloor \frac{(2*m+1)^2}{2} \rfloor = (m+1)^2$ .

So, our $2013 \times 2013$ chessboard there are $2014^2$ black squares.

Now, since we have the basics covered lets approach the problem in a simple way. at first when I approached this problem I had no idea how to start. And when you don't know how to start just consider a simpler case and play around with it. Experiment with it as long as you like. So, what is simpler than a $2013 \times 2013$ chessboard? A $3 \times 3$ chessboard! So, I drew a $3 \times 3$ board with black squares on the corner and tried to cover it with imaginary triminoes. And after a few seconds it became clear that it is impossible to cover it with non over lapping triminoes. Same, goes for a $5 \times 5$ chessboard.[At this point I just gave the answer $0$ and they said that it was wrong!]

Then, I focused on $7 \times 7$ chessboard and finally I found that we can cover all the black squares with $16$ non-overlapping triminoes if the black squares were in the corners. I figured that with $2$ non over lapping triminoes I can make a $2 \times 3$ rectangle and with one I can make a shape that is not a $2 \times 2$ square but they can cover the same number of black squares as a $2 \times 2$ square can.

These are the shapes that we can make

And, I divided the $7 \times 7$ chessboard according to the following picture:

That way I could easily cover all the black squares and that required the minimum number of triminoes.

So, I made a conjecture that for any odd $n > 5$ the minimum number of triminoes required to cover its black squares if the corner square was black equaled to $\frac{(n+1)^2}{4}$ .

Since, I proved my conjecture for $7$ my base case was already proved. Then, I assumed that it was true for some odd positive integer $k$ .

So, now my goal is to prove that it is true for $k+2$ . See this image:

We can divide a $(k+2) \times (k+2)$ into a $k \times k$ , a $(k+2) \times 2$ and a $k \times 2$ board as the image.

Now each of the rectangles can be covered with the shapes that we talked about. We can cover all the black squares of the $k \times 2$ rectangle with $\frac{(k-3)}{2}$ triminoes and one $3 \times 2$ rectangle. So, the minimum number of triminoes required to cover that is $\frac{(k-3)}{2} + 2$ .

Similarly, we can divide $(k+2) \times 2$ rectangle into a $2 \times k$ rectangle and a $2 \times 2$ squares. The minimum numbers of triminoes required to cover the black squares of this is $\frac{(k-3)}{2} + 2 + 2$ .

So, the minimum number of non- overlapping trimonoes required to cover all the black squares where the corner squares are black $(k+2) \times (k+2)$ board is equal to $\frac{(k+1)^2}{4} + \frac{(k-3)}{2} + 2 + \frac{(k-3)}{2} + 2 + 2 = \frac{(k+3)^2}{4}$ .

So, the minimum number of non-overlapping triminoes required to cover our board is $\frac{(2013+1)^2}{4} = 1007^2$ .

Now, $1007 \equiv 7 mod1000$

So, $1007^2 \equiv 49 mod 1000$ .

So, the answer is $49$ .

It's 1007*1005+2014=1014049..It's really very easy..