Sunday, December 24, 2006

Gimme That! Topic: Sets. Level: AIME/Olympiad.

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 $ \{1, 2, \ldots, n\} $ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.

Solution: We define $ S_n $ to be the desired number. Trying small cases, we get

$ S_1 = 1: \{1\} $

$ S_2 = 1: \{1\} $

$ S_3 = 2: \{1\}; \{2, 3\} $

$ S_4 = 3: \{1\}; \{2, 3\}; \{2, 4\} $

$ S_5 = 5 $ and $ S_6 = 8 $.

Well now we're tempted to say that $ S_n = F_n $, the $ n $th Fibonnaci number (with $ F_1 = F_2 = 1 $). To do so, we want to find a bijection between the minimal selfish subsets of $ T_n = \{1, 2, \ldots, n\} $ and the minimal selfish subsets of $ T_{n-1} = \{1, 2, \ldots, n-1\} $ and $ T_{n-2} = \{1, 2, \ldots, n-2\} $.

Clearly all the minimal selfish subsets of $ T_{n-1} $ are in $ T_n $ as well. The remaining minimal selfish subsets of $ T_n $ are those which contain the element $ n $. Consider the following bijection between the minimal selfish subsets of $ T_n $ containing $ n $ and the minimal selfish subsets of $ T_{n-2} $:

$ P = \{a_1, a_2, \ldots, a_k, n\} \leftrightarrow Q = \{a_1-1, a_2-1, \ldots, a_k-1\} $.

Clearly $ a_i > 1 $ because otherwise $ \{a_i\} $ would be a selfish subset. Also, $ a_k \le n-1 $. Hence the mapping works both ways; it remains to show that if one is a minimal selfish subset, so is the other. Since $ |P| = |Q|+1 $, we know that both are selfish or neither of them is. Furthermore, if $ P $ contains a selfish subset $ \{b_1, b_2, \ldots, b_k\} $, $ Q $ will contain the selfish subset $ \{b_1-1, b_2-1, \ldots, b_{k-1}-1\} $ and if $ Q $ contains the selfish subset $ \{c_1, c_2, \ldots, c_k\} $ then $ P $ will contain the selfish subset $ \{c_1+1, c_2+1, \ldots, c_k+1, n\} $. So the bijection works.

That means we have $ S_n = S_{n-1}+S_{n-2} $ so $ S_n = F_n $, 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 $ A $ such that for any two squares of combined area $ 1 $, a rectangle of area $ A $ 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 comments:

  1. 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

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

    ReplyDelete
  3. 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}

    ReplyDelete
  4. 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.

    ReplyDelete
  5. Heh, yeah, it's kinda annoying, I know. Nice solution, though.

    ReplyDelete