PUMaC 2012 · 代数（A 组） · 第 6 题
PUMaC 2012 — Algebra (Division A) — Problem 6
题目详情
- [ 6 ] Let a be a sequence such that a = 0 and: n 0 a = a + 1 = a + 1 3 n +1 3 n n a = a + 2 = a + 2 3 n +2 3 n n for all natural numbers n . How many n less than 2012 have the property that a = 7? n √ 1
解析
- [ 6 ] Let a be a sequence such that a = 0 and: n 0 a = a + 1 = a + 1 3 n +1 3 n n a = a + 2 = a + 2 3 n +2 3 n n for all natural numbers n . How many n less than 2012 have the property that a = 7? n Solution: Let f ( n ) = a . n In the end we obtain that f ( n ) represents the sum of the digits of n in the representation in base 3. To reach that, first we see that: n n = 3 b c + r, 3 where r ∈ { 1 , 2 } . Thus, n n f ( n ) = f (3 b c + r ) = f (3 b c ) + r 3 3 n n n = f ( b c ) + r = f ( b c ) + n − 3 b c 3 3 3 n b c n n 3 We can also apply this to b c instead of n , taking into consideration that b c = b c . 2 3 3 3 Thus, n n f ( n ) = f ( b c ) + n − 3 b c 3 3 n n n n = f ( b c ) + b c − 3 b c + n − 3 b c 2 2 3 3 3 3 n n n = f ( b c ) + n − 2 b c − 3 b c 2 2 3 3 3 n n n = ... = f ( b c ) + n − 2 b c − 2 b c − ... k 2 3 3 3 n n ... − 2 b c − 3 b c k − 1 k 3 3 3 n n n For k large enough, b c = 0, so f ( n ) = n − 2 b c − 2 b c − ... , which is exactly the sum of 2 k 3 3 2 the digits of n written in base 3. So the problem now is just how many numbers less than 2012 have, in base 3, the sum of their digits 7, which is easy to find. We will do the counting in base 3. Number 2012 in base 3 is 2202112, so every number smaller than 2012 will need to have at most 7 digits. Case 1: how many numbers have 3 of its digits 2, one digit 1 and three 0? We assume we have 7 positions and each digits occupies one of these positions (note: 0 can ( )( ) 7 4 be the first digit, and we just neglect it). This arrangement can be done in ways; from 3 1 these, we have to subtract the numbers greater than 2202112. If one such number starts with ( ) 4 222, the rest can be continued in ways. If the number starts with 221, the rest can be 1 ( ) 4 completed in ways. Thus, there are 132 numbers smaller than 2202112 with three of the 1 digits 2. Case 2: how many numbers have 2 of their digits 2, 3 digits 1 and 2 digits 0? ( )( ) 7 5 Again, we assume we have to fill in the 7 positions. That can be done in ways. From 2 2 these numbers we have to subtract the ones larger than 2202112, thus the ones that start with ( ) 4
- Those that start with 221 can be completed in ways, so we get that there are 204 2 numbers smaller than 2202112 which have two of their digits 2. Case 3: how many numbers have one of their digits 2, five digits 1 and one 0? ( )( ) 7 6 We can form numbers, and all of them are smaller than 2202122, so we get 42 numbers. 1 1 Case 4: how many numbers have no digit 2 and seven digits 1? Only one, 1111111. By adding, we get 132 + 204 + 42 + 1 = 379 numbers which have the sum of their digits in base 3 seven, and are smaller than 2012. Answer: 379 √ 1