PUMaC 2023 · 个人决赛（B 组） · 第 1 题
PUMaC 2023 — Individual Finals (Division B) — Problem 1
题目详情
- For a binary string S (i.e. a string of 0’s and 1’s) that contains at least one 0, we produce a binary string f ( S ) as follows: • If the substring 110 occurs in S , replace each instance of 110 with 01 to produce f ( S ); • Otherwise, replace the leftmost occurrence of 0 in S by 1 to produce f ( S ). Given binary string S of length n , we define the lifetime of S to be the number of times f can be applied to S until the resulting string contains no more 0’s. For example, 111000 → 10100 → 11100 → 1010 → 1110 → 101 → 111 so the lifetime of 111000 is 6. For a given n ≥ 2, which binary string(s) of length n have the longest lifetime? As usual, you need to rigorously justify your answers.
解析
- For a binary string S (i.e. a string of 0’s and 1’s) that contains at least one 0, we produce a binary string f ( S ) as follows: • If the substring 110 occurs in S , replace each instance of 110 with 01 to produce f ( S ); • Otherwise, replace the leftmost occurrence of 0 in S by 1 to produce f ( S ). Given binary string S of length n , we define the lifetime of S to be the number of times f can be applied to S until the resulting string contains no more 0’s. For example, 111000 → 10100 → 11100 → 1010 → 1110 → 101 → 111 so the lifetime of 111000 is 6. For a given n ≥ 2, which binary string(s) of length n have the longest lifetime? Proposed by Austen Mazenko Solution: Let g ( S ) = # { 0’s in S } + # { length of S } . Importantly, g ( f ( S )) ≤ g ( S ) − 1: ap- plying f to S will decrease its g -value by at least 1. If we replace 110 by 01 in the string, k times, then g ( S ) decreases by k , and if we replace 0 by 1, g ( S ) decreases by 1. Claim: Applying f to S = 00 ... 0, m times, will decrease the g -value by exactly m . Proof: The only ‘forms’ of strings we can get from applying f repeatedly are 00 ... 00, 100 .. 00, 1100 ... 00, and 0100 ... 00. Applying f to any of these forms will bring you to another form. The only time we decrease g by 2 or more, is when we change 110 to 01 in 2 or more spots in the string, which never happens among these forms. So, g decreases by 1 every time. Once we have this, S = 00 ... 00 ( n zeros) has the highest initial g -value (of 2 n ), and only n decreases by 1 each time. Its final g -value is at most 2 (since all of its possible ‘forms’ have at most 2 1’s in it). Note that any string of length ≥ 2 can never change into the string ‘1’ after applications of f . So, S has the highest possible initial g -value out of all length- n strings, has n the lowest possible final g -value, and its g -value decreases the slowest, so its lifetime must be maximal, and its lifetime is 2 n − 2 (its g value decreases from 2 n to 2, decreasing by exactly 1 under every application of f ).