HMMT 二月 2025 · COMB 赛 · 第 7 题
HMMT February 2025 — COMB Round — Problem 7
题目详情
- Compute the number of ways to arrange 3 copies of each of the 26 lowercase letters of the English alphabet such that for any two distinct letters x and x , the number of x ’s between the first and 1 2 2 second occurrences of x equals the number of x ’s between the second and third occurrences of x . 1 2 1
解析
- Compute the number of ways to arrange 3 copies of each of the 26 lowercase letters of the English alphabet such that for any two distinct letters x and x , the number of x ’s between the first and 1 2 2 second occurrences of x equals the number of x ’s between the second and third occurrences of x . 1 2 1 Proposed by: Derek Liu 25 Answer: 2 26! Solution: First, we prove such a string can be divided into blocks where each block consists of the same substring written three times. We prove the following lemma. Lemma 1. For any letter x , the strings between the first and second occurrences of x and between 1 1 the second and third occurrences of x are the same. 1 Proof. Call these two strings s and s . We know they must be permutations of each other, and if a 1 2 letter appears twice in s , it would also have to appear twice in s , for four appearances in all, which 1 2 is impossible. Thus, no letter appears twice in s (and likewise in s ). 1 2 Assume for sake of contradiction that for some letters x and x in these strings, x appears before x 2 3 2 3 in s , but after x in s . Then, between these two appearances of x (which are consecutive, because 1 3 2 2 no other x ’s appear in either s or s ), there must be two x ’s. This implies there must also be two 2 1 2 3 x ’s between the other pair of consecutive x ’s, contradiction. 3 2 We conclude any two letters in s and s appear in the same order in both strings, so s = s . 1 2 1 2 Let the first letter of our 78-character string be x , and suppose the next appearance of x is the 1 1 ( k + 1)-th letter. Let x , x , . . . , x be the letters in between. Then, x x . . . x is the string between 2 3 k 2 3 k the first and second x ’s, so it must also be the string between the second and third x ’s. Thus, after 1 1 the second x , we must have x x . . . x x . 1 2 3 k 1 Now, between the first and second x ’s is the string x x x . . . x , so this must also be between the k 1 2 3 k − 1 second and third x ’s. Thus, after the second x , we must have x x x . . . x . k k 1 2 3 k Thus, the first 3 k letters are simply x x x . . . x repeated three times. We can remove this block of 1 2 3 k 3 k letters and repeat to show that the whole string can be divided into such blocks. 25 To count the number of such strings, we first note that there are 2 ways to divide the strings into such blocks. This is because there are 25 possible places which can divide two blocks (after the 3rd, 6th, 9th, etc. letters), and we can choose any subset of these to divide blocks. The string is then uniquely determined by the first one-third of each block, which must consist of every letter exactly once (as the whole string is just three copies of these thirds spliced together). These thirds can consist of any ordering of the 26 letters, so there are 26! strings with any given partition of blocks. 25 We conclude the total number of strings is 2 · 26! . Remark. Another way to see the characterization of strings is as follows. First, solve the problem for the case of two letters a and b : it is straightforward to show that the only strings are ababab , bababa , aaabbb , bbbaaa . Going back to the original problem, the six appearances of any pair of letters must be in the order of one of the four strings above; say two letters are interleaved if they alternate appearances. Construct a graph on letters with an edge between two letters if and only if they are interleaved. Note that if a and b are interleaved, and b and c are interleaved, then a and c must be interleaved. Thus, the graph is transitive, implying that it is a union of disjoint cliques. We can now finish as before.