PUMaC 2020 · 团队赛 · 第 10 题
PUMaC 2020 — Team Round — Problem 10
题目详情
- Let N be the number of sequences of positive integers greater than 1 where the product of all 64 b of the terms of the sequence is 12 . If N can be expressed as a (2 ) , where a is an odd positive integer, determine b.
解析
- Let N be the number of sequences of positive integers greater than 1 where the product of all 64 b of the terms of the sequence is 12 . If N can be expressed as a (2 ) , where a is an odd positive integer, determine b. Proposed by: Frank Lu Answer: 128 Let g ( n ) be the number of ordered tuples of any size so that the entries multiply to n, and all are positive integers that are at least 2 . Let f ( n ) be the sum over all such ordered tuples of the sum of the entries in the tuples. For sake of convenience, we set g (1) = 1 , representing how we have the empty product of a tuple of length 0 , and similarly we have that f (1) = 0 , representing the empty sum. ∑ Then, we see that, summing over possible first entries, yields us that g ( n ) = g ( d ) . We’ll d | n,d 6 = n ∑ write this as 2 g ( n ) = g ( d ) We also know that g ( p ) = 1 for any prime p, as we have that the d | n only ordered tuple is ( p ) . k k − 1 By a similar logic, we can see that g ( p ) = 2 , by using an inductive argument. a b Now, observe that, given n = p q , where p, q are distinct primes and a, b ≥ 1 , that we have ∑ ∑ ∑ ∑ that 2 g ( n ) = g ( n ) + g ( d ) = g ( n ) + g ( d ) + g ( d ) − g ( d ) = 2 g ( n/p ) + 2 g ( n/q ) − d | n d | n/p d | n/q d | n/pq 2 g ( n/pq ) . We thus see that g ( n ) = 2 g ( n/p ) + 2 g ( n/q ) − 2 g ( n/pq ) , unless n = pq, where in this case we have that g ( pq ) = 3 . a b g ( p q ) a Now, let f ( a ) = . Note then that our recurrence relation becomes 2 f ( a + 1) = b a − 1 b +1 2 a a +1 a 2 f ( a ) + 2 f ( a + 1) − 2 f ( a ) , or that f ( a + 1) − f ( a ) = 2 f ( a + 1) − f ( a ) , unless b +1 b b b +1 b +1 b b we have both a, b equaling zero, where then we have that f (1) = 3 . 1 This yields us, for a, b where at least one of a, b is greater than 1 , that f ( a ) − f (0) = b b ∑ a − 1 b b − 1 2 f ( i + 1) − f ( i ) . But f (0) = g ( q ) , which for b > 1 is equal to 2 , so in fact this b − 1 b − 1 b i =0 ∑ a becomes f ( a ) − f (0) = f ( a ) − f (0) + f ( i ). But we can then rewrite this as b b b − 1 b − 1 b − 1 i =1 ∑ a f ( a ) = f ( a ) + 2 f ( i ) , for all positive integers a and for b > 1 , and for b = 1 , a > 1 . b b − 1 b − 1 i =0 We can thus see that, with f ( a ) = 1 for a 6 = 0 that f ( a ) = a + 2 . Note that f will be a 0 1 b degree b polynomial. ( ) ∑ b a + i Now, suppose we can write f ( a ) = c , for some coefficients i. It thus follows that b i i =0 i ( ) ( ) ( ) ( ) ( ) ∑ ∑ ∑ ∑ ∑ b a b b b a + i j + i a + i a + i +1 a f ( a ) = c + c = c + c = c + b +1 i i i i 0 i =0 j =0 i =0 i =0 i =0 i i i i +1 0 ( ) ( ) ∑ b a + b +1 a + i c + ( c + c ) . b i i − 1 i =1 b +1 i But starting with the fact that the coefficients begin as 1 , 1, with a +2 = a +1+1 , it thus follows ( )( ) ( )( ) ∑ ∑ b b b a + i b a + i a b a − 1 that we have that f ( a ) = , giving us in turn that g ( p q ) = 2 ( ) . b i =0 i =0 i i i i 128 64 Applying this to our situation, we want to evaluate f (2 3 ) . We can express this then as ( )( ) ∑ 64 64 128+ i 127 2 ( ) . Note that in this sum inner sum, we have two terms whose largest i =0 i i power of 2 dividing them is 1 , namely i = 0 , i = 64 , and one term whose largest power of 2 ( )( ) ( ) 64 128+32 196 dividing them is 2 , namely . Their sum is + 1 . But note that this is divisible 32 32 64 by 4 , yielding us the answer 128. To see this, consider the product (192 ∗ 191 ∗ 190 ∗ . . . ∗
- / (64 ∗ 63 ∗ . . . ∗ 1) . Observe then that we can pair elements together in the denominator by i and 64 − i, and pairing i and 320 − i, save for the elements 192 , 64 , 160 , 32 . Only one of these is equivalent to 3 (mod 4) when the largest power of 2 is divided out. This is then equivalent ( ) 196 to 3 (mod 4) , showing that + 1 is at least divisible by 4 . 64