HMMT 十一月 2018 · 冲刺赛 · 第 21 题

HMMT November 2018 — Guts Round — Problem 21

[ 11 ] A function f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } is said to be nasty if there do not exist distinct a, b ∈ { 1 , 2 , 3 , 4 , 5 } satisfying f ( a ) = b and f ( b ) = a . How many nasty functions are there? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2018, November 10, 2018 — GUTS ROUND Organization Team Team ID#

解析

[ 11 ] A function f : { 1 , 2 , 3 , 4 , 5 } ! { 1 , 2 , 3 , 4 , 5 } is said to be nasty if there do not exist distinct a, b 2 { 1 , 2 , 3 , 4 , 5 } satisfying f ( a ) = b and f ( b ) = a . How many nasty functions are there? Proposed by: Michael Ren Answer: 1950 5 We use complementary counting. There are 5 = 3125 total functions. If there is at least one pair of 5 3 numbers which map to each other, there are = 10 ways to choose the pair and 5 = 125 ways to 2 assign the other values of the function for a total of 1250. But we overcount each time there are two such pairs, so we must subtract o ↵ 5 · 3 · 5 = 75, where there are 5 options for which number is not in a pair, 3 options for how the other four numbers are paired up, and 5 options for where the function outputs when the unpaired number is inputted. This results in a final answer of 3125 (1250 75) = 1950.