PUMaC 2012 · 团队赛 · 第 9 题

PUMaC 2012 — Team Round — Problem 9

(4 digits) I have a random number machine generator that is very good at generating integers between 1 and 256, inclusive, with equal probability. However, right now, I want to produce a random number between 1 and n , inclusive, so I do the following: • I use my machine to generate a number between 1 and 256. Call this a . • I take a and divide it by n to get remainder r . If r 6 = 0, then I record r as the randomly generated number. If r = 0, then I record n instead. Note that this process does not necessarily produce all numbers with equal probability, but that is okay. I apply this process twice to generate two numbers randomly between 1 and 10. 16 Let p be the probability that the two numbers are equal. What is p · 2 ?

解析

Problem: (4 digits) Define the following: ∑ ∞ 1 • A = 6 n =1 n ∑ ∞ 1 • B = 6 n =1 n +1 ∑ ∞ 1 • C = 6 n =1 ( n +1) ∑ ∞ 1 • D = 6 n =1 (2 n − 1) ∑ ∞ 1 • E = 6 n =1 (2 n +1) B C D E Consider the ratios , , , . Exactly one of the four is a rational number. Let that number A A A A be r/s , where r and s are nonnegative integers and gcd( r, s ) = 1. Concatenate r, s . 6 π (It might be helpful to know that A = .) 945 Answer: 6364 Solution: We want to see if we can rewrite the sums of B, C, D, E in terms of A somehow. It’s not really obvious what to do with B , so we skip that one. With C , we have: ( ) ∞ ∑ 1 1 1 1 1 1 1 1 C = = + + + · · · = + + + + · · · − 1 = A − 1 6 6 6 6 6 6 6 6 ( n + 1) 2 3 4 1 2 3 4 n =1 C A − 1 1 C So = = 1 − . Since A is not rational, neither is . For D , we have: A A A A ∞ ∑ 1 1 1 1 D = = + + + · · · 6 6 6 6 (2 n − 1) 1 3 5 n =1 These are the odd terms in the sum for A . If we try to separate the odd terms from the even terms in A , we get: ( ) ( ) ∞ ∑ 1 1 1 1 1 1 1 1 1 A = = + + + + . . . = + + . . . + + + . . . 6 6 6 6 6 6 6 6 6 n 1 2 3 4 1 3 2 4 n =1 6 Note that: ( ) 1 1 1 1 1 1

- . . . = + + . . . = A 6 6 6 6 6 6 2 4 2 1 2 2 1 D 63 Thus, we have A = D + A , which gives = , which is rational. Thus, the answer is 6 2 A 64 6364 . E Note that E = D − 1, so is not rational. A Author: Alan