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 distincta, 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 ∈ { 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 distincta, 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
We use complementary counting. There are 5 = 3125 total functions. If there is at least one pair of 5
numbers which map to each other, there are = 10 ways to choose the pair and 5 = 125 ways to 35
assign the other values of the function for a total of 1250. But we overcount each time there are two such 2
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 outputswhen the unpaired number is inputted. This results in a final answer of 3125 (1250 75) = 1950.