返回题库

HMMT 二月 2018 · 团队赛 · 第 7 题

HMMT February 2018 — Team Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 50 ] Let [ n ] denote the set of integers { 1 , 2 , . . . , n } . We randomly choose a function f : [ n ] → [ n ],
    out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Findnb c kthe probability that there exist positive integers b, c ≥ 1 such that f (1) = a and f ( a ) = 1. ( f ( x )
    denotes the result of applying f to x k times).
解析

英文解析

  1. [ 50 ] Let [ n ] denote the set of integers { 1 , 2 , . . . , n } . We randomly choose a function f : [ n ] → [ n ],
    out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Findnb c kthe probability that there exist positive integers b, c ≥ 1 such that f (1) = a and f ( a ) = 1. ( f ( x )
    denotes the result of applying f to x k times).
    Proposed by: Allen Liu
    Answer:1
    Given a function f , define N ( f ) to be the number of numbers that are in the same cycle as 1 (including 1 nitself), if there is one, and zero if there is no such cycle. The problem is equivalent to finding E ( N ( f )) /n .
    Note thatn − 1 n − 2 n − k + 1 1
    P ( N ( f ) = k ) = · · · · · · · ,
    n n n nn
    ∑
    and it suffices to compute P where P = P ( N ( f ) = k ). Observe thatkk kk =1 n
    ( )
    n − 1 n − 2 3 2 1 n 1
    P = · · · · · · · · · ·
    n n n n n n nn
    ( )
    n − 1 n − 2 3 2 n − 1 1
    P = · · · · · · · · ·
    n − 1
    n n n n n n
    ( )
    n − 1 n − 2 3 2 1
    ⇒ P + P = · · · · · · · ·
    n n − 1
    n n n n n
    ( )
    n − 1 n − 2 3 n − 2 1
    P = · · · · · · · ·
    n − 2
    n n n n n
    ( )
    n − 1 n − 2 3 1
    ⇒ P + P + P = · · · · · · ·
    n n − 1 n − 2
    n n n n
    · · ·
    ∑n
    ⇒ P = 1 ·1
    k =1 nk
    Therefore the answer is .1 n