HMMT 十一月 2021 · 冲刺赛 · 第 24 题
HMMT November 2021 — Guts Round — Problem 24
题目详情
- [12] Find the number of subsets S of { 1 , 2 , . . . , 48 } satisfying both of the following properties: • For each integer 1 ≤ k ≤ 24, exactly one of 2 k − 1 and 2 k is in S . • There are exactly nine integers 1 ≤ m ≤ 47 so that both m and m + 1 are in S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2021, November 13, 2021 — GUTS ROUND Organization Team Team ID#
解析
- [12] Find the number of subsets S of { 1 , 2 , . . . , 48 } satisfying both of the following properties: • For each integer 1 ≤ k ≤ 24, exactly one of 2 k − 1 and 2 k is in S . • There are exactly nine integers 1 ≤ m ≤ 47 so that both m and m + 1 are in S . Proposed by: Daniel Zhu Answer: 177100 Solution: This problem can be thought of as laying down a series of 1 × 2 dominoes, with each one having either the left or right square marked. The second condition states that exactly 9 pairs of con- secutive dominoes will have the leftmost one with the right square marked and the rightmost one with the left square marked. Therefore, this problem can be thought of as laying down a series of dominoes with the left square marked, followed by a series with the right square marked, followed by left square and so on and so forth, with the pattern LRLRLRL...LR. However, the left end is not guaranteed to be left marked dominoes and the right end is not guaranteed to be right marked dominoes. However, we can add a left marked domino to the left end and a right marked domino to the right end without changing the number of right-left combinations in the sequence. Further, there will be 10 of each left and right blocks, and a total of 26 dominoes, such that each block has at least 1 domino. If there are a , a , ..., a dominoes in each block, then a + a + ... + a = 26 and a > 0 for all 1 ≤ i ≤ 20 . 1 2 20 1 2 20 i ( ) 25 Therefore, from stars and bars, we find that there are ways to select the dominoes and thus the 6 ( ) 25 subset S. Surprisingly, is not too hard to compute and is just 177100 . 6