PUMaC 2020 · 团队赛 · 第 6 题
PUMaC 2020 — Team Round — Problem 6
题目详情
- We say that a string of digits from 0 to 9 is valid if the following conditions hold: First, for 2 ≤ k ≤ 4 , no consecutive run of k digits sums to a multiple of 10 . Second, between any two 0s, there are at least 3 other digits. Find the last four digits of the number of valid strings of length 2020 .
解析
- We say that a string of digits from 0 to 9 is valid if the following conditions hold: First, for 2 ≤ k ≤ 4 , no consecutive run of k digits sums to a multiple of 10 . Second, between any two 0s, there are at least 3 other digits. Find the last four digits of the number of valid strings of length 2020 . Proposed by: Frank Lu Answer: 9040 Let a be the number of valid strings of length l whose last digit is 0 , and define b to be those l l whose second to last digit is 0 , c third to last digit is 0 , and d to be all other valid strings. l l Let t = a + b + c + d . l l l l l Then, observe that we can construct the following recurrences: First, a = d , as for any valid string where there is no 0 in the last three digits, we can l l − 1 append a 0 to get a valid string. This holds for l ≥ 2 . Next, b = 7 a . To see this, suppose we have a valid string ending with a 0 of length l l − 1 l − 1 , whose last three digits are x, y, 0 . Then, we can add any digit except for 0 , and the digits equivalent to − y and − x − y (mod 10) , all of which are distinct. By a similar logic, c = 7 b . l l − 1 Note, however, that these equations only hold for l ≥ 4 . Finally, we note that d = 7 c + 6 d , by applying a similar logic. Summing all of these l l − 1 l − 1 up, we see that t = 7 t . We do, however, need to compute t first, as we’ve seen that this l l − 1 3 recurrence only holds for l ≥ 4 . We compute: a = 1 , d = 9 , b = c = 0 . For l = 2 : a = 1 1 1 1 2 9 , b = 9 , c = 0 , d = 72 , and for l = 3 : a = 72 , b = 72 , c = 72 , d = 504 . This yields that 2 2 2 3 3 3 3 l − 3 t = 10 , t = 90 , t = 720 , which gives us that for l ≥ 4 , t = 720 · 7 , which gives us that 1 2 3 l 2017 t = 720 · 7 . 2020 Now, to compute the last four digits: we see that this is equivalent to 0 (mod 16) , so we need 500 to find what it is (mod 625) . Note that 7 ≡ 1 (mod 625) , by Euler totient, which gives us 17 17 that t ≡ 95 · 7 (mod 625) . But as this is divisible by 5 , we can just find what 19 · 7 2020 4 16 4 (mod 125) is. However, we see that 7 = 2401 ≡ 25 + 1 (mod 125) , so hence 7 ≡ (25 + 1) ≡ 17 1+25 · 4 ≡ 101 (mod 125) . But then we have that 19 · 7 ≡ 133 · 101 ≡ 58 (mod 125) , implying that t ≡ 290 (mod 625) . Noting that we have that t is divisible by 16 yields us that 2020 2020 t ’s last four digits are 9040 . 2020