HMMT 二月 2016 · COMB 赛 · 第 7 题
HMMT February 2016 — COMB Round — Problem 7
题目详情
- Kelvin the Frog has a pair of standard fair 8-sided dice (each labelled from 1 to 8). Alex the sketchy Kat also has a pair of fair 8-sided dice, but whose faces are labelled differently (the integers on each Alex’s dice need not be distinct). To Alex’s dismay, when both Kelvin and Alex roll their dice, the probability that they get any given sum is equal! Suppose that Alex’s two dice have a and b total dots on them, respectively. Assuming that a 6 = b , find all possible values of min { a, b } .
解析
- Kelvin the Frog has a pair of standard fair 8-sided dice (each labelled from 1 to 8). Alex the sketchy Kat also has a pair of fair 8-sided dice, but whose faces are labelled differently (the integers on each Alex’s dice need not be distinct). To Alex’s dismay, when both Kelvin and Alex roll their dice, the probability that they get any given sum is equal! Suppose that Alex’s two dice have a and b total dots on them, respectively. Assuming that a 6 = b , find all possible values of min { a, b } . Proposed by: Alexander Katz Answer: 24, 28, 32 Ed. note: I’m probably horribly abusing notation Define the generating function of an event A as the polynomial ∑ i g ( A, x ) = p x i where p denotes the probability that i occurs during event A . We note that the generating is multi- i plicative; i.e. ∑ i + j g ( A AND B, x ) = g ( A ) g ( B ) = p q x i j where q denotes the probability that j occurs during event B . j In our case, events A and B are the rolling of the first and second dice, respectively, so the generating functions are the same: 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 g (die , x ) = x + x + x + x + x + x + x + x 8 8 8 8 8 8 8 8 and so 1 2 1 2 3 4 5 6 7 8 2 g (both dice rolled , x ) = g (die , x ) = ( x + x + x + x + x + x + x + x ) 64 i where the coefficient of x denotes the probability of rolling a sum of i . We wish to find two alternate dice, C and D , satisfying the following conditions: • C and D are both 8-sided dice; i.e. the sum of the coefficients of g ( C, x ) and g ( D, x ) are both 8 (or g ( C, 1) = g ( D, 1) = 8). • The faces of C and D are all labeled with a positive integer; i.e. the powers of each term of g ( C, x ) and g ( D, x ) are positive integer (or g ( C, 0) = g ( D, 0) = 0). • The probability of rolling any given sum upon rolling C and D is equal to the probability of rolling any given sum upon rolling A and B ; i.e. g ( C, x ) g ( D, x ) = g ( A, x ) g ( B, x ). 1 Because the dice are “fair” – i.e. the probability of rolling any face is – we can multiply g ( A, x ) , g ( B, x ) , g ( C, x ) 8 and g ( D, x ) by 8 to get integer polynomials; as this does not affect any of the conditions, we can as- 1 2 8 2 sume g ( C, x ) and g ( D, x ) are integer polynomials multiplying to ( x + x + . . . + x ) (and subject to the other two conditions as well). Since Z is a UFD (i.e. integer polynomials can be expressed as the product of integer polynomials in exactly one way, up to order and scaling by a constant), all 1 2 8 factors of g ( C, x ) and g ( D, x ) must also be factors of x + x + . . . + x . Hence it is useful to factor 1 2 8 2 4 x + x + . . . + x = x ( x + 1)( x + 1)( x + 1). 2 2 2 2 4 2 We thus have g ( C, x ) g ( D, x ) = x ( x + 1) ( x + 1) ( x + 1) . We know that g ( C, 0) = g ( D, 0) = 0, so 2 2 2 4 2 x | g ( C, x ) , g ( D, x ). It remains to distribute the remaining term ( x + 1) ( x + 1) ( x + 1) ; we can view each of these 6 factors as being “assigned” to either C or D . Note that since g ( C, 1) = g ( D, 1) = 8, 2 4 and each of the factors x + 1 , x + 1 , x + 1 evaluates to 2 when x = 1, exactly three factors must be 2 4 assigned to C and exactly three to D . Finally, assigning x + 1 , x + 1 , and x + 1 to C results in the standard die, with a = b = 28.. This gives us the three cases (and their permutations): 2 2 2 4 2 5 • g ( C, x ) = x ( x + 1) ( x + 1), g ( D, x ) = x ( x + 1)( x + 1) . In this case we get g ( C, x ) = x + 4 3 2 11 9 7 5 3 2 x + 2 x + 2 x + x and g ( D, x ) = x + x + 2 x + 2 x + x + x , so the “smaller” die has faces 5 , 4 , 4 , 3 , 3 , 2 , 2 , and 1 which sum to 24. 2 2 4 2 • g ( C, x ) = x ( x + 1)( x + 1) , g ( D, x ) = x ( x + 1)( x + 1) . In this case we have g ( C, x ) = 6 5 4 3 2 10 9 6 5 2 x + x + 2 x + 2 x + x + x and g ( D, x ) = x + x + 2 x + 2 x + x + x , so the “smaller” die has faces 6 , 5 , 4 , 4 , 3 , 3 , 2 and 1 which sum to 28. 2 2 4 2 4 • g ( C, x ) = x ( x + 1) ( x + 1) , g ( D, x ) = x ( x + 1) ( x + 1). In this case we have g ( C, x ) = 9 7 5 3 7 6 5 3 2 x + 2 x + 2 x + 2 x + x and g ( D, x ) = x + 2 x + x + x + 2 x + x , so the “smaller die” has faces 7 , 6 , 6 , 5 , 3 , 2 , 2 , 1 which sum to 32. Therefore, min { a, b } is equal to 24 , 28 , or 32 .