Problem:
A special deck of cards contains cards, each labeled with a number from to and colored with one of seven colors. Each number-color combination appears on exactly one card. Sharon will select a set of eight cards from the deck at random. Given that she gets at least one card of each color and at least one card with each number, the probability that Sharon can discard one of her cards and still have at least one card of each color and at least one card with each number is , where and are relatively prime positive integers. Find .
Solution:
In a set of eight cards that includes every color and every number, there will be exactly one repeated number and exactly one repeated color. If Sharon selects a set that includes the card with that number and color, Sharon can discard it. If the set does not include that card, Sharon cannot discard any card.
In the former case, there are ways to choose one card of each number and color, and then ways to choose the "extra" card. The total is .
In the latter case, there are ways to choose which number is repeated, and ways to choose which two cards of that number are used. There are then ways to choose which color is repeated, and ways to choose which cards of that color are used. There now remain four unused colors and four unused numbers, and there are ways to choose from those. The total is .
The probability that a given set is of the first type is therefore . The requested sum is .
The problems on this page are the property of the MAA's American Mathematics Competitions