# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Gimme That! Topic: Sets. Level: AIME/Olympiad. December 24th, 2006

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

and .

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.

### 5 Responses to “Gimme That! Topic: Sets. Level: AIME/Olympiad.”

1. DrIdiot Says:

i did it this way.

let a n-selfish set be a selfish set with cardinality n

you can show
a n-selfish set S is minimal iff k is an element of S implies that k >= n
=> easy to show that if k > n you can find a subset of S that is also selfish

Yeah, I figured out how to show that, but where do you go from there to get S_n = F_n?

3. DrIdiot Says:

let a n-selfish set be a selfish set with cardinality n

you can show
a n-selfish set S is minimal iff k is an element of S implies that k >= n
=> easy to show that if k > n you can find a subset of S that is also selfish
<= a n-selfish set must have n as an element. so a m-selfish subset of S must have m < n as its element but this cant be true.

so number of k-minimal subsets of S_n = \binom{n – k}{k – 1}
then you just have to show that
\sum_{k = 1}^n \binom{n – k}{k – 1} = F_n

which just requires knowing \binom{a}{b} + \binom{a}{b – 1} = \binom}{a + 1}{b}

4. DrIdiot Says:

okay. so uh, could you delete my posts 3-6 because uh…

okay so apparently HTML tags are allowed in here so when i typed in the less than sign it tried to interpret it as an HTML tag… which didn’t work so great and ended up making stuff get “deleted”. so instead if just used ampersand-lt-semicolon to get the less than sign. thats why my first post got cut off. sorry about that.