PUMaC 2019 · 组合（A 组） · 第 8 题
PUMaC 2019 — Combinatorics (Division A) — Problem 8
题目详情
- Let S be the set of points ( x/ 2 , y/ 2) ∈ R such that x, y are odd integers and | x | ≤ y ≤ 2 n . n Let T be the number of graphs G with vertex set S satisfying the following conditions: n n 1 • G has no cycles. • If two points share an edge, then the distance between them is 1. • For any path P = ( a, . . . , b ) in G , the smallest y -coordinate among the points in P is either that of a or that of b . However, multiple points may share this y -coordinate. Find the 100th-smallest positive integer n such that the units digit of T is 4. 3 n 2
解析
- Let S be the set of points ( x/ 2 , y/ 2) ∈ R such that x, y are odd integers and | x | ≤ y ≤ 2 n . n Let T be the number of graphs G with vertex set S satisfying the following conditions: n n • G has no cycles. • If two points share an edge, then the distance between them is 1. • For any path P = ( a, . . . , b ) in G , the smallest y -coordinate among the points in P is either that of a or that of b . However, multiple points may share this y -coordinate. Find the 100th-smallest positive integer n such that the units digit of T is 4. 3 n Proposed by Michael Gintz. Answer: 399 . Solution: Note that S is just an upside-down pyramid. We wish to show that we can build n G one row at a time from the biggest row. Note that if we do this, and we build a row, we have some partition of the row into segments, and each segment has at most one vertical line coming up from it. Note that then regardless of what lies above, if it follows the conditions in 3 the problem then when we add these edges we will still follow the conditions in the problem. Now we can look at this inductively. We wish to see how many ways f ( k ) there are to build a row of length k (where k might be odd). Note that we must partition the row into segments, decide whether each segment gets a vertical line, and if it does where it goes. Then there are x + 1 options for vertical lines for a segment of length x . Thus for x ≥ 1 we can build this inductively based on the size of the first segment: f ( x ) = 2 f ( x − 1) + 3 f ( x − 2) + . . . + ( x + 1) f (0) . Thus we can add and subtract f ( x − 1) from this so for x ≥ 2 we have f ( x ) = 3 f ( x − 1) + f ( x − 2) + . . . + f (0) . Finally we can add and subtract f ( x − 1) again so for x ≥ 3 we have f ( x ) = 4 f ( x − 1) − 2 f ( x − 2) . We then have f (0) = 1 , f (1) = 2 , f (2) = 7 and we can build the rest from this last rule. Now note that 2 n − 1 T = f (2) × f (4) × . . . × f (2 n − 2) × 2 , n 2 n − 1 where the 2 comes from the number of ways to partition the biggest row, with two choices for every adjacent pair. Let us list out the first few values of f mod 10. Starting from f (0) we have 1 , 2 , 7 , 4 , 2 , 0 , 6 , 4 , 4 , 8 , 4 , 0 , 2 , . . . Thus we see that f (6 + x ) ≡ 2 f ( x ) (mod 10) for x > 3. Now we wish to take the product of the even ones. Note that for x ≥ 2 we have 6 T ≡ 2 f (2 x ) f (2 x + 2) f (2 x + 4) T x +3 x x − 4 Note that when x is 1,2,3 mod 3, the values of these products of f are equivalent to 2 × 2 , x − 2 x − 3 8 × 2 and 6 × 2 . Now note that we can calculate the last digits of T through T as 2, 1 4 6, 8, 2. Thus we have for x ≥ 0 we have 6 x x 3 x ( x +1) / 2 6 x 3 x ( x +1) / 2 T ≡ 8 × 2 6 2 ≡ 8 × 2 × 2 3 x +3 We know that the second term cycles through 6,4 and the third cycles through 6,8,2,4,4,2,8,6 so T cycles starting at x = 0 through 8,6,6,8,2,4,4,2. Thus each 8-cycle has 2 fours. Thus 3 x +3 we want to be in the fiftieth cycle and take the seventh element which is T so our 3 × (8 × 49+6) answer is 8 × 49 + 7 = 399. 4