HMMT 十一月 2021 · THM 赛 · 第 4 题
HMMT November 2021 — THM Round — Problem 4
题目详情
- Let n be the answer to this problem. We define the digit sum of a date as the sum of its 4 digits when expressed in mmdd format (e.g. the digit sum of 13 May is 0+5+1+3 = 9). Find the number of dates in the year 2021 with digit sum equal to the positive integer n . n 2
解析
- Let n be the answer to this problem. We define the digit sum of a date as the sum of its 4 digits when expressed in mmdd format (e.g. the digit sum of 13 May is 0+5+1+3 = 9). Find the number of dates in the year 2021 with digit sum equal to the positive integer n . Proposed by: Sheldon Kieren Tan Answer: 15 Solution: This problem is an exercise in how to do ugly computations efficiently. Let f ( n ) be the number of days with digit sum n . Also, let g ( n ) be the number of days with digit sum n , under the assumption that every month has 30 days. Let h ( n ) be the number of positive integers from 1 to 30 with integer sum n . We now do computation: n 1 2 3 4 5 6 7 8 9 10 11 h ( n ) 2 3 4 3 3 3 3 3 3 2 1 ∑ ∑ 3 9 Observe that g ( n ) = 2 h ( n − k ) + h ( n − k ). Also, to move from g ( n ) to f ( n ) we need to k =1 k =4 add in “01-31”, “03-31”, “05-31”, “07-31”, “08-31”, “10-31”, “12-31” and subtract “02-29”, “02-30”. Therefore we find n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ∑ 3 h ( n − k ) 2 5 9 10 10 9 9 9 9 8 6 3 1 k =1 ∑ 9 h ( n − k ) 2 5 9 12 15 18 19 19 18 17 15 12 9 6 3 1 k =4 g ( n ) 4 10 18 22 25 27 30 33 36 35 31 24 19 15 12 9 6 3 1 f ( n ) 4 10 18 23 25 29 30 34 36 36 32 23 19 15 12 9 6 3 1 Evidently the answer is 15. While the above computation is a bit tedious in practice, the work one has to do can be dramatically cut down if one notices that if n ≤ 10 or so, f ( n ) is significantly larger than n . Thus one only really needs to compute the latter half of the table. n 2