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

HMMT November 2011 — Guts Round — Problem 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 ways can he order the problems for his test? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 4 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 12 NOVEMBER 2011 — GUTS ROUND Round 5

解析

[ 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 ways can 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 th i j problem. 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