PUMaC 2011 · 组合（A 组） · 第 7 题
PUMaC 2011 — Combinatorics (Division A) — Problem 7
题目详情
- [ 7 ] At the start of the PUMaC opening ceremony in McCosh auditorium, the speaker counts 90 people in the audience. Every minute afterwards, either one person enters the auditorium (due to waking up late) or leaves (in order to take a dreadful math contest). The speaker observes that in this time, exactly 100 people enter the auditorium, 100 leave, and 100 was m the largest audience size he saw. Find the largest integer m such that 2 divides the number of different possible sequences of entries and exits given the above information.
解析
- Define a such that if in the i th minute from the beginning someone enters, then a = 1 , and i i if someone leaves, then a = − 1. Hence, each possible sequence of entries and exits is denoted i n ∑ 200 by a sequence { a } containing 100 values of 1 and 100 values of − 1. Define S = a for i n i i =1 i =1 0 ≤ n ≤ 200, and M = max S . First consider the number of possible sequences for which i 1 ≤ i ≤ 200 M ≥ 10. If a sequence { a } has M ≥ 10, we can find i such that S = 10, since S = 0 and every S n i 0 i differs by 1 from the previous one. Let p be the minimum of these such i ’s, so that S = 10 p and S < 10 for any i < p . Now define another sequence { b } such that i i { − a if i ≤ p, i b = . i a if i > p i Then, this forms a bijection between all such sequences { a } with M ≥ 10 to all such sequences n 200 { b } containing 90 values of 1 and 110 values of − 1’s, since it is not hard to check that i i =1 this “reflection” is one-to-one and onto. (Essentially what we are doing is noting that for any random walk with 200 steps of ± 1 starting at 90, ending at 90, and going above 100, then we can reflect the sequence after the first time the sequence goes above 100, which gives a random ( ) 200 walk starting at 90 and ending at 110.) Here, the number of sequences { b } is , so the i 90 ( ) 200 number of { a } with M ≥ 10 is also . n 90 ( ) 200 Similarly, the number of { a } with M ≥ 11 is . Subtracting the two gives the number of i 89 sequences { a } with M = 10. This exactly satisfies the requirement of the problem, since the i maximum number of people at any time is 90 + 10 = 100. Also, the number of people will not be negative, otherwise the number of people cannot reach 100 at any time. So ( ) ( ) 200 200 21 × 200! n = − = . 90 89 90! × 111! The greatest power of 2 in a factorial k ! is given by Legendre’s formula to be ⌊ ⌋ b log k c 2 ∑ k v ( k !) = , 2 i 2 i =1 3 so calculating the powers in these three factorials, m = v (200!) − v (90!) − v (111!) = 197 − 2 2 2 86 − 105 = 6 .