Suppose you have a 10 10 checkerboard and a deck of 2 2 cards with
Question:
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
Project Management A Managerial Approach
ISBN: 978-0470226216
7th Edition
Authors: Jack R. Meredith, Samuel J. Mantel,