Domino Tiling of square grid after removing pair of cells

Revision en1, by yesnomaybe, 2020-10-19 16:14:39

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.

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English yesnomaybe 2020-10-19 16:15:24 29 Tiny change: ' GoodPair.\n\nProbl' -> ' GoodPair. Count number of good pairs.\n\nProbl'
en1 English yesnomaybe 2020-10-19 16:14:39 903 Initial revision (published)