HMMT 十一月 2021 · 冲刺赛 · 第 36 题
HMMT November 2021 — Guts Round — Problem 36
题目详情
- [20] Let N be the number of ways in which the letters in “HMMTHMMTHMMTHMMTHMMTHMMT” (“HMMT” repeated six times) can be rearranged so that each letter is adjacent to another copy of the same letter. For example, “MMMMMMTTTTTTHHHHHHHHHHHH” satisfies this property, but “HMMMMMTTTTTTHHHHHHHHHHHM” does not. Estimate N . ⌊ ⌋ ( ) 4 N E An estimate of E will earn 20 min , points. E N
解析
- [20] Let N be the number of ways in which the letters in “HMMTHMMTHMMTHMMTHMMTH- MMT” (“HMMT” repeated six times) can be rearranged so that each letter is adjacent to another copy of the same letter. For example, “MMMMMMTTTTTTHHHHHHHHHHHH” satisfies this property, but “HMMMMMTTTTTTHHHHHHHHHHHM” does not. Estimate N . ⌊ ⌋ ( ) 4 N E An estimate of E will earn 20 min , points. E N Proposed by: David Vulakh, Sean Li Answer: 78556 Solution: We first count the number of arrangements for which each block of consecutive identical letters has even size. Pair up the letters into 3 pairs of H , 6 pairs of M , and 3 pairs of T , then rearrange 12! the pairs. There are = 18480 ways to do this. 6!3!3! In the original problem, we may estimate the number of arrangements by computing the fraction of arrangements with all even blocks. We estimate this by counting the number of ways to split the 6 Hs, 12 Ms, and 6 Ts into blocks, and collating the proportions of splittings which use all even blocks: • We can split 6 as 6, 4 + 2, 3 + 3, and 2 + 4. Exactly 3 / 4 of the splittings have all even blocks. • We can split 12 into 12, 10 + 2, . . . , 2 + 10, 8 + 2 + 2, 7 + 3 + 2, 6 + 4 + 2, 5 + 5 + 2, 6 + 3 + 3, 5 + 4 + 3, 6 + 2 + 2 + 2, 5 + 3 + 2 + 2, 4 + 4 + 2 + 2, 4 + 3 + 3 + 2, 3 + 3 + 3 + 3, 4 + 2 + 2 + 2 + 2, 3 + 3 + 2 + 2 + 2, 2 + 2 + 2 + 2 + 2 + 2. Stars and bars to expand from the pairs variant gives 79000 The following C++ code outputs the exact answer: #include <bits/stdc++.h> using namespace std; #define IJK iii[0]][iii[1]][iii[2] #define ijk i][j][k #define MAX_N 100 #define S 3 #define N 6 long long dp[2][3][MAX_N][MAX_N][MAX_N]; int main() { dp[1][0][0][0][0] = 1; for (int i = 0; i <= N; i++) for (int j = 0; j <= 2*N; j++) for (int k = 0; k <= N; k++) for (int c = 0; c < S; c++) for (int l = 0; l < S; l++) { int iii[] = { i, j, k }; iii[l]++; dp[0][l][IJK] += (c != l || !(i + j + k)) * dp[1][c][ijk]; dp[1][l][IJK] += (c == l && i + j + k) * (dp[1][c][ijk] + dp[0][c][ijk]); } long long a = 0; for (int i = 0; i < S; i++) a += dp[1][i][N][2 * N][N]; cout << a << endl; return 0; }