PUMaC 2021 · 组合（A 组） · 第 1 题
PUMaC 2021 — Combinatorics (Division A) — Problem 1
题目详情
(1) (2) (3) (4) ( j ) ( j ) splits into four new atoms, a , a , a , a . Atoms a and a are entangled if and only i i i i i k 1 ( j ) ( j +1) if the atoms a and a were entangled after n minutes. Moreover, atoms a and a are i k i k entangled for all 1 ≤ i, k ≤ N and j = 1 , 2 , 3. Therefore, after one minute there is 4 atoms, after two minutes there are 16 atoms and so on. Physicists are now interested in the number of unordered quadruplets of atoms { b , b , b , b } 1 2 3 4 among which there is an odd number of entanglements. What is the number of such quadru- plets after 3 minutes? Remark. Note that atom entanglement is not transitive. In other words, if atoms a , a i j are entangled and if a , a are entangled, this does not necessarily mean that a and a are j k i k entangled. 2
解析
- Select two distinct diagonals at random from a regular octagon. What is the probability that the two diagonals intersect at a point strictly within the octagon? Express your answer as a a + b , where the probability is and a and b are relatively prime positive integers. b Proposed by: Rishi Dange Answer: 26 7 The answer is . We use complementary counting. 19 Split into three cases in which the diagonals don’t intersect strictly within the octagon. Case 1: The diagonals intersect on the octagon. For each vertex, there are 5 possible diagonals 5 from which we must choose 2 in this case. This gives us 8 = 80 total ways. 2 Case 2: The diagonals never intersect. Take a diagonal separated by 1 vertex. There are 2 other diagonals parallel to this one. There are 4 distinct possible rotations, giving a total of 3 4 = 12 possibilities. The only other way for the diagonals to not intersect is to take a 2 diagonal separated by 2 vertices, in which case there is only 1 parallel choice and 4 rotations. Thus, we have a total of 12 + 4 = 16 ways for this case. Case 3: The diagonals intersect outside of the octagon. There are two subcases here. First, we can have two non-parallel diagonals that are each separated by 1 vertex. By rotation, there are 8 ways for this. Second, we can have one diagonal separated by 1 vertex and one separated by 2. For each possible diagonal separated by 1 vertex, there are 2 possibilities for the other diagonal. Thus, we have 8 × 2 = 16 possibilities here. That gives us a total of 8 + 16 = 24 ways for this case. The total number of ways to select diagonals that do not intersect strictly within the octagon 20 8 × 5 is 80 + 16 + 24 = 120. There are = 20 diagonals, giving = 190 total choices. Thus, 2 2 120 7 by complementary counting, we arrive at a final answer of 1 − = . 190 19