PUMaC 2023 · 团队赛 · 第 15 题
PUMaC 2023 — Team Round — Problem 15
题目详情
- Let a denote the number of ternary strings of length n so that there does not exist a k < n n such that the first k digits of the string equals the last k digits. What is the largest integer m m such that 3 | a ? 2023 Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 2
解析
- Let a denote the number of ternary strings of length n so that there does not exist a k < n n such that the first k digits of the string equals the last k digits. What is the largest integer m m such that 3 | a ? 2023 Austen Mazenko Answer: 9 We claim that a satisfies the following recursive relations: a = 3 a and a = 3 a − n 2 n +1 2 n 2 n 2 n − 1 a . Such strings satisfying this criterion are known as bifix-free . n We begin with the observation that if some string s is not-bifix free, then it’s possible to find n a k ≤ such that the first k digits of s equals its last k digits. Suppose the length of the 2 n ′ minimal substring s of s that is both a prefix and suffix for it is length k > . Thus, the 2 ′ ′ ′ prefix s and suffix s must overlap in 2 k − n ≥ 1 values, so the last 2 k − n digits of s equal ′ its first 2 k − n digits. But, because s is a prefix and suffix of s , we see that this means the ′′ first 2 k − n digits of s equal its last 2 k − n digits. We have thus found a substring s of length ′ 2 k − n < k that is both a prefix and suffix of s , contradicting minimality of s . To see why a = 3 a , notice first that if s is a length 2 n bifix-free string, then inserting any 2 n +1 2 n ′ digit right in the middle gives another bifix-free string s , because from our earlier observation 7 ′ if s has any bifix, then it must have a bifix of length ≤ n which means it doesn’t include the interpolated digit and thus would have been a bifix for s . Analogous reasoning show that ′ any bifix-free string t of length 2 n + 1 can be mapped to a bifix-free string t of length 2 n by removing its middle digit. This establishes a one-to-three mapping between length 2 n and length 2 n + 1 bifix-free strings, so a = 3 a . 2 n +1 2 n To see why a = 3 a − a , we will demonstrate a one-to-three mapping between length 2 n 2 n − 1 n 2 n − 1 bifix-free strings and the union of the set of 2 n bifix-free strings with the set of length 2 n strings which are the concatenation of two copies of the same length n bifix-free string. First, for any bifix-free string s of length 2 n − 1, we can insert any digit into its n th position ′ 3 different ways. Now, the resulting length 2 n string s can’t have any bifix of length ≤ n − 1 ′ because then it would be a bifix of s . Thus, either s is a length 2 n bifix or it has a bifix of length n , aka, its first n digit substring equals its latter n digit substring. Moreover, we see ′′ this substring s must itself be bifix-free of length n because any bifix it has is a bifix of length ′ ≤ n − 1 of s , but we showed this was impossible. It remains to see that any length 2 n bifix-free string and any concatenation of a length n bifix-free string with itself can be constructed this way. Indeed, removing the n th digit from a length 2 n bifix-free string must result in a bifix-free string, because if the result isn’t bifix-free then it would have a bifix of length at most n − 1 which would thus be a bifix of the original string. The same argument applies to the other case, whence the mapping is one-to-three, as claimed. Therefore, 3 · a = a + a . 2 n − 1 n 2 n Note a = 3 , a = 6. To finish the problem, we remark that ν ( a ) is the number of ones in the 1 2 3 n binary representation of n . This can be proven by strong induction. The base cases obviously hold. Now, suppose it holds up to a . If n is even, then n + 1 has one more binary 1 than n n , and indeed a = 3 a = ⇒ ν ( a ) = 1 + ν ( a ). If n is odd, then from the recursive n +1 n 3 n +1 3 n relation for a we have ν ( a ) = ν (3 a − a ). If ν (3 a ) ̸ = ν ( a ), then we see n 3 n +1 3 n ( n +1) / 2 3 n 3 ( n +1) / 2 ν ( a ) = min { 1 + ν ( a ) , ν ( a ) } . Note that, to get from ( n + 1) / 2 to n in binary, you 3 n +1 3 n 3 ( n +1) / 2 append a 0 to the right, then replace all the trailing zeros with ones and the rightmost one with a zero. In particular, this process either keeps the numbers of ones the same or raises it. Thus, by the inductive hypothesis, ν (3 a ) ̸ = ν ( a ) always holds, so ν ( a ) = ν ( a ), 3 n 3 3 n +1 3 ( n +1) / 2 ( n +1) / 2 which by the inductive hypothesis is precisely the number of ones in the binary representation of ( n + 1) / 2 which equals the number of ones in the binary representation of n + 1, as desired. Thus, ν ( a ) is the number of ones in the binary representation 2023 = 11111100111 , 3 2023 2 namely, 9. 8