The task of the employer

Every boss wants to have at his disposal only the best people. Therefore, to give a job he personally evaluates intelligence of each, not trusting the content of the diploma. Here is one of the classical problems in these interviews: "The 8 \times 8 checkerboard cut two cells in opposite corners (lower left and upper right or upper left and lower right). Is it possible to tile completely the rest of the board by dominoes, with size of 1 \times 2 cells?". At first glance it seems that it is possible, since the number of remaining cells is even (64-2 = 62), but if you look closely, you will notice that each domino covers one white and one black cell (regardless of how we placed it on the board). And in opposite corners of the cells are always the same colors, so some dominoes would not have matching cells to cover — hence, the correct answer is impossible.

Now the bosses are smarter. They cut any cells they like, leaving the same question: "Is it possible to completely cover the rest of the board by dominoes?".