PUMaC 2012 · 组合（A 组） · 第 7 题
PUMaC 2012 — Combinatorics (Division A) — Problem 7
题目详情
- [ 7 ] A PUMaC grader is grading the submissions of forty students s , s , . . . , s for the individ- 1 2 40 ual finals round, which has three problems. After grading a problem of student s , the grader i either: • grades another problem of the same student, or • grades the same problem of the student s or s (if i > 1 and i < 40, respectively). i − 1 i +1 He grades each problem exactly once, starting with the first problem of s and ending with 1 the third problem of s . Let N be the number of different orders the grader may grade the 40 students’ problems in this way. Find the remainder when N is divided by 100.
解析
- Equivalently, consider a Hamiltonian walk on the squares of a cylindrical 3 × 40 chessboard (wrapped so that the two long sides overlap). Let A denote the number of ways to start at the n top left corner (1 , 3) of such a 3 × n cylindrically-wrapped chessboard and end in the bottom right corner ( n, 1), and let B denote the number of ways to start at the top left corner (1 , 3) n and end in the top right corner ( n, 3). Then the question is asking for the value of B . The 40 key is the two recurrence relations n − 1 n − 1 ∑ ∑ A = 1 + A + B , B = 2 A (*) n i i n i i =0 i =0 This comes from the observation that for any path starting on the left side and ending on the right side, if there were k horizontal steps before reaching the destination point on the right side, then the previous 2 k + 1 moves before those are also fixed upto two possibilities: · · · · · · This holds true for each value of k from 0 to n − 2. Note that that the number of paths from column 1 to column n is then reduced to counting the number of paths from column 1 to column n − k − 1, upto a change in the row. The one exception is when k = n − 1, in which 3 case we end up with a valid path of the entire 3 × n board if the destination is not in the first row (hence the +1 in ( ∗ )). When we keep track of the row change, we obtain the recursions in ( ∗ ) - recall the cylindrical nature of the chessboard means that there is symmetry in the cases of the bottom two rows. It thus suffices to solve ( ∗ ). Notice that A − A = A + B , B − B = 2 A . n +1 n n n n +1 n n Substituting the first equation into the second one gives ( A − 2 A ) − ( A − 2 A ) = 2 A = ⇒ A = 3 A . n +2 n +1 n +1 n n n +2 n +1 n − 2 Hence, for all n > 1, one has the explicit formula A = 3 A . With a bit of casework and n 2 n − 2 visualization, we indeed see that A = 1 , A = 2 , A = 6 , · · · , so A = 2 · 3 for all n > 1. 1 2 3 n 1 4 38 Thus, the desired answer is the value of A = 2 · 3 (mod 100) . Since ϕ (100) = · · 100 = 40, 40 2 5 40 Euler’s totient theorem shows that 3 ≡ 1 (mod 100). Also, we note that 1 ≡ 201 ≡ 3 · 67 (mod 100), so ( ) 2 38 − 1 2 A = 2 · 3 ≡ 2 · 3 ≡ 2 · 67 ≡ 8978 ≡ 78 (mod 100) . 40 − 1