Maths Olympiad Prep

Library / /447 of 860

Algebra Difficulty 5.2 AIME, harder Find the answer

How many functions f:{1,2,3,4,5}{1,2,3,4,5}f:\{1,2,3,4,5\} \rightarrow\{1,2,3,4,5\} have the property that f({1,2,3})f(\{1,2,3\}) and f(f({1,2,3}))f(f(\{1,2,3\})) are disjoint?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let f({1,2,3})f(\{1,2,3\}) be AA. Then Af(A)=A \cap f(A)=\emptyset, so AA must be a subset of {4,5}\{4,5\}. If B={4,5}B=\{4,5\}, there are 2322^{3}-2 ways to assign each element in {1,2,3}\{1,2,3\} to a value in {4,5}\{4,5\}, and 9 ways to assign each element of {4,5}\{4,5\} to a value in {1,2,3}\{1,2,3\}, for a total of 54 choices of ff. If A={4}A=\{4\}, there is 1 possible value for each element of {1,2,3},4\{1,2,3\}, 4 ways to assign {4}\{4\} with a value from {1,2,3,5}\{1,2,3,5\}, and 5 ways to assign a value to {5}\{5\}. Similarly, if A={5}A=\{5\}, there are 45=204 \cdot 5=20 choices for ff. In total, there are 54+202=9454+20 \cdot 2=94 possible functions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.