Emissary Puzzles

I’ve been invited to help with the Puzzle Column at the MSRI newsletter Emissary. We prepared six puzzles for the Fall 2018 issue.

I love the puzzles there. Number 2 is a mafia puzzle that I suggested. Number 6 is a fun variation on the hat puzzle I wrote a lot about. Here is puzzle Number 3.

Puzzle. Let A = {1,2,3,4,5} and let P be the set of all nonempty subsets of A. A function f from P to A is a “selector” function if f(B) is in B, and f(B union C) is either equal to f(B) or f(C). How many selector functions are there?

Share:

6 Comments

5!

2. Gregory Marton:

Well, least it’s such a selector, and there 5! permutations of the arbitrary ordering that function uses, so I’ll agree with Konstantin, but I don’t know how to prove that any other selector has to be equivalent to one of those.

3. Serge Resnick:

By induction on the number 5 ðŸ™‚

4. Ashley Hoober:

Are we sure we aren’t dealing with any equivalent sectors? 5 seems logical as it was my conclusion as well.

five

6. Austin:

Proof that the answer is 5!:

Let us say f({1,2,3,4,5}) = 5, for instance. Then I claim that for every B âŠ† A such that B contains 5, we must have f(B) = 5. The reason is that B has a complement B’, and f({1,2,3,4,5}) must equal either f(B) or f(B’). But f(B’) cannot be 5, so f(B) must be 5.

Now let us say f({1,2,3,4}) = 4, for instance. Then similar reasoning shows that f(B) = 4 for every B containing 4 but not 5. We may continue in this manner. Of course the selection of 5 and 4 above was arbitrary; what it comes to is that there must be some ranking of the numbers 1, 2, 3, 4, 5, such that f(B) is the highest-ranked element of B. The number of such rankings is 5! and each gives rise to a unique selector function. Thus there are 5! selector functions.