Problem: (1996 Putnam – B1) Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
Solution: We define to be the desired number. Trying small cases, we get
Well now we’re tempted to say that , the th Fibonnaci number (with ). To do so, we want to find a bijection between the minimal selfish subsets of and the minimal selfish subsets of and .
Clearly all the minimal selfish subsets of are in as well. The remaining minimal selfish subsets of are those which contain the element . Consider the following bijection between the minimal selfish subsets of containing and the minimal selfish subsets of :
Clearly because otherwise would be a selfish subset. Also, . Hence the mapping works both ways; it remains to show that if one is a minimal selfish subset, so is the other. Since , we know that both are selfish or neither of them is. Furthermore, if contains a selfish subset , will contain the selfish subset and if contains the selfish subset then will contain the selfish subset . So the bijection works.
That means we have so , as desired. QED.
Comment: Decently hard for a B1, at the least the part that involved rigorously proving that the mapping is actually a bijection. It was pretty easy to figure out what the answer was, but as usual much more difficult to prove it.
Practice Problem: (1996 Putnam – A1) Find the least number such that for any two squares of combined area , a rectangle of area exists such that the two squares can be packed in the rectangle (without interior overlap). You may assume that the sides of the squares are parallel to the sides of the rectangle.
Leave a Reply
You must be logged in to post a comment.