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
: 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 0 = 1, u 1 = 3, so we may now use the relation to calculate successively 8, 21, 55, 144, 377, 987, 2584, 6765, 17711 (= u 10 ). 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 0 , u 0 , v 1 , u 1 , ... is Fibonacci. 51st Putnam 1990 © John Scholes jscholes@kalva.demon.co.uk 1 Jan 2001