Problem of the Week 995

A Choice Problem

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Let A = {1, 2, 3, 4, 5} and let P be the set of all nonempty subsets of A. A function f:P -> A is a selector function if f(B) is in B and for every B and C, f(B union C) is either f(B) or f(C). How many selector functions are there?

Of course, readers might want to figure out the number of such functions when A = {1,2,3,....,n}.

Source: Suggested by Dan Velleman (Amherst College) who saw it on a Turkish national contest from 1998.

© Copyright 2003 Stan Wagon. Reproduced with permission.