HMMT 十一月 2011 · 冲刺赛 · 第 12 题

英文解析

12. [ 8 ] Joe has written 5 questions of different difficulties for a test with problems numbered 1 though 5.
    He wants to make sure that problem i is harder than problem j whenever i − j ≥ 3. In how many wayscan he order the problems for his test?
    Answer: 25 We will write p > p for integers i, j when the i th problem is harder than the j thi jproblem. For the problem conditions to be true, we must have p > p , p > p , and p > p .
    4 1 5 2 5 1
    Then, out of 5! = 120 total orderings, we see that in half of them satisfy p > p and half satisfy
    4 1
    ( ) ( )
    1 1
    p > p , and that these two events occur independently. Hence, there are (120) = 30 orderings
    5 2
    2 2
    4!
    which satisfy the first two conditions. Then, we see that there are = 6 orderings of p , p , p , p
    1 2 4 5
    2!2!
    which work; of these, only p > p > p > p violates the condition p > p . Consequently, we have
    4 1 5 2 5 1 5