### 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

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 uN be the solution for the general case. Let vN be the solution with the restriction that B does not contain the element N. Let wN be the solution with the restriction that B does contain the element N. We seek recurrence relations.

First observe that wN = uN-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 uN = vN + wN, so vN = uN - uN-1.

Now consider uN+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 uN 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 vN possibilities for case (2). Similarly for case (3). For case (4) we use the correspondence (A, B) ↔ (A', B') to show that there are uN-1 possibilities. Thus we have finally: uN+1 = uN + 2vN + uN-1 = 3uN - uN-1.

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

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

Alternatively, we may notice that the relations above may be rewritten as uN = vN + uN-1 and vN = uN-1 + vN-1, which (together with the starting values), shows that v0, u0, v1, u1, ... is Fibonacci.