Suppose you have a 10 × 10 checkerboard and a deck of 2 × 2 cards with squares that match the size of the squares of the checkerboard, so 25 of these cards can be used to completely cover the checkerboard. If we allow the cards to overlap each other, there are many ways to cover the checkerboard. We say that an arrangement of cards is a covering if all of the cards in the arrangement are lined up with the squares on the checkerboard, and they are completely on the checkerboard, possibly overlapping, and every square of the checkerboard has at least one card on top of it. We call a covering of the checkerboard redundant if one of the cards can be removed and the checkerboard is still covered. A covering of the checkerboard is non-redundant if it is no longer a covering if any card is removed. Clearly, the smallest non-redundant covering has 25 cards. The aim of this problem is to find bounds on the number of cards in the largest possible non-redundant covering.

a) Show that there is a non-redundant covering with 35 cards.

b) Show that every covering with 55 cards is redundant.

c) Can you improve these bounds