Putnam 1990/A6 solution

51st Putnam 1990

Problem A6

How many ordered pairs (A, B) of subsets of {1, 2, ... , 10} can we find such that each element of A is larger than |B| and each element of B is larger than |A|.

Solution

Answer: 17711.

Evidently we are meant to solve the general case of subsets of {1, 2, ... , N}. But the choice of N = 10 is poor, because it is sufficiently small to be tractable and in an exam it is certainly safer to slog it out for the specific case, rather than to risk failing to find a more elegant solution in the limited time available. Thus if A has 0 elements, then B can be anything, so we have 1024 possibilities. If A has 1 element, then we have 10C1 9C0 + 9C1 9C1 + 8C1 9C2 + ... + 1C1 9C9 = 2816 possibilities. If A has 2 elements, then we have 10C2 8C0 + 9C2 8C1 + ... + 2C2 8C8 = 4096 possibilities and so on.

Let u_N be the solution for the general case. Let v_N be the solution with the restriction that B does not contain the element N. Let w_N be the solution with the restriction that B does contain the element N. We seek recurrence relations.

First observe that w_N = u_N-1 because we have the correspondence (A, B) ↔ (A', B - {N}), where A' is the set derived from A by reducing each element by 1. Obviously u_N = v_N + w_N, so v_N = u_N - u_N-1.

Now consider u_N+1. There are four cases: (1) neither A nor B contains N+1, (2) A contains N+1, but B does not, (3) B contains N+1, but A does not, (4) both A and B contain N+1. Clearly, there are u_N possibilities in case (1). In case (2) we have the correspondence (A, B) ↔ (A - {N+1}, B'), where B' is derived from B by reducing each element by 1. This shows that there are v_N possibilities for case (2). Similarly for case (3). For case (4) we use the correspondence (A, B) ↔ (A', B') to show that there are u_N-1 possibilities. Thus we have finally: u_N+1 = u_N + 2v_N + u_N-1 = 3u_N - u_N-1.

Clearly, u₀ = 1, u₁ = 3, so we may now use the relation to calculate successively 8, 21, 55, 144, 377, 987, 2584, 6765, 17711 (= u₁₀).

We may recognize these as alternate Fibonacci numbers and indeed a little thought shows that if a_n+2 = a_n+1 + a_n then a_n+2 = 2a_n + a_n-1 = 2a_n + (a_n - a_n-2) = 3a_n - a_n-2.

Alternatively, we may notice that the relations above may be rewritten as u_N = v_N + u_N-1 and v_N = u_N-1 + v_N-1, which (together with the starting values), shows that v₀, u₀, v₁, u₁, ... is Fibonacci.

51st Putnam 1990