PUMaC 2015 · 组合（A 组） · 第 4 题

PUMaC 2015 — Combinatorics (Division A) — Problem 4

[ 4 ] A number is interesting if it is a 6-digit integer that contains no zeros, its first 3 digits are strictly increasing, and its last 3 digits are non-increasing. What is the average of all interesting numbers?

解析

[ 4 ] A number is interesting if it is a 6-digit integer that contains no zeros, its first 3 digits are strictly increasing, and its last 3 digits are non-increasing. What is the average of all interesting numbers? Solution: We calculate the expected value of each digit, then use linearity of expectation to find the total expected value. Let a , a , a , a , a , a denote the expected value of each digit 1 2 3 4 5 6 and let the expected value be a = a a a a a a . By symmetry, we have a = a = 5. and 1 2 3 4 5 6 2 5 a + a = a + a = 10. 1 3 4 6 If a = k , then a , a ∈ { k + 1 , . . . , 9 } and ( a , a ) correspond to the number of ways: 1 2 3 2 3 ( ) 9 − k (9 − k − 1) + (9 − k − 2) + . . . + 1 = 2 To choose two numbers among { k +1 , . . . , 9 } , so calculating and using the hockey stick identity: ( ) ( ) ( ) ( ) ( ) ( ) ( ) 8 7 2 9 8 3 10 1 · + 2 · + . . . + 7 · + + . . . + 10 5 2 2 2 3 3 3 4 ( ) ( ) ( ) ( ) ( ) a = = = = = 1 8 7 2 9 9 4 2

- . . . + 2 2 2 3 3 If a = k , then a , a ∈ { k, . . . , 9 } and ( a , a ) correspond to the number of ways: 6 5 4 5 4 ( ) 9 − k + 2 (9 − k + 1) + (9 − k ) + . . . + 1 = 2 To choose two numbers among { k, . . . , 9 } allowing replacement, so calculating and using the hockey stick identity: ( ) ( ) ( ) ( ) ( ) ( ) ( ) 10 9 2 11 10 3 12 1 · + 2 · + . . . + 9 · + + . . . + 12 2 2 2 3 3 3 4 ( ) ( ) ( ) ( ) ( ) a = = = = = 3 6 10 9 2 11 11 4
- . . . + 2 2 2 3 3 Then it follows that a = a a a a a a = 250000 + 50000 + 7500 + 700 + 50 + 3 = 308253 . 1 2 3 4 5 6 Authors: Victor Zhou, Bill Huang