Problem : You are given a NxN matrix and consider if a pair of cells is removed from the square matrix and then if we are able to cover remaining cells of the matrix by a 1x2 tile placing it either horizontally or vertically then the pair of cell removed is called GoodPair. Count number of good pairs.
Problem link : https://www.codechef.com/LOGI2020/problems/CHEFG999
Solution : The given square matrix can be visualised as a NxN chessboard with cells of black and white colour. So we can say that if one pair of cell with opposite colours is removed then only the solution is possible. (As domino tiling matches one black cell with one white cell or vice versa).
I understand that we need to remove cells with different parity of (i+j), but is it ALWAYS possible? Can someone explain the proof of it or provide a constructive approach to lay out the tiles?
The first thing to note is that if N is odd, there are no good pairs.
Secondly we note (as you say) that by a colouring argument, we obviously cannot have a good pair if the (i+j) values have the same parity.
So it remains to find a construction that works for any even value of N, and any pair with different (i+j) parities.
This is not a proof, but I will outline my construction with the aid of this picture: https://ibb.co/5BJ6Wh7
Note that since the points of the pair are distinct, then at least one of two things holds: either i1 != i2, or j1 != j2, or both.
Suppose abs(i2-i1) is even (possibly zero), then abs(j2-j1) must be odd, since i2+j2-i1-j1 is odd. Similarly is abs(i2-i1) is odd, then abs(j2-j1) is even.
Without loss of generality, I will demonstrate a construction assuming that abs(i2-i1) is odd, and the same solution can be rotated 90 degrees if abs(i2-i1) is even (since abs(j2-j1) must be odd in that case).
Again without loss of generality, say i1 < i2. Then all rows i < i1 and i > i2 can be covered by horizontal tiles (green in my picture).
Note that in rows i1 and i2, there are now only N-1 cells to be covered. This means that on one side of the cell (i1,j1), there is a gap of an even number of cells (possibly zero), and on the other side there is an odd number of cells. In each row, let's cover the even side with horizontal tiles. Since i1 != i2 mod 2, we know j1 = j2 mod 2, so the even gap is on the same side in row i1 as it is in row i2.
On the odd side, use horizontal tiles until the very last cell, then a vertical tile into the next row (either i1+1 or i2-1). Then iteratively fill each row with horizontal tiles until the last cell, with one vertical tile into the subsequent row, and so on. The coverings are blue in my picture. Since the parity of i1 is different to i2, these will eventually meet without conflict.