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.
Share: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?
Konstantin Knop:
5!
3 March 2019, 2:45 pmGregory 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 March 2019, 9:25 pmSerge Resnick:
By induction on the number 5 🙂
4 March 2019, 8:37 amAshley Hoober:
Are we sure we aren’t dealing with any equivalent sectors? 5 seems logical as it was my conclusion as well.
10 March 2019, 2:40 pmBella Marin:
five
10 March 2019, 2:41 pmAustin:
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.
18 March 2019, 12:29 pm