HMMT 十一月 2017 · 冲刺赛 · 第 34 题
HMMT November 2017 — Guts Round — Problem 34
题目详情
- [ 30 ] The skeletal structure of circumcircumcircumcoronene, a hydrocarbon with the chemical formula C H , is shown below. 150 30 Each line segment between two atoms is at least a single bond. However, since each carbon (C) requires exactly four bonds connected to it and each hydrogen (H) requires exactly one bond, some of the line segments are actually double bonds. How many arrangements of single/double bonds are there such that the above requirements are satisfied? (Rotations and reflections of the same arrangement are considered distinct.) ∣ ∣ (⌊ ( )⌋ ) ∣ ∣ A If the correct answer is C and your answer is A , you get max 30 1 − log , 0 points. ∣ ∣ log C C 2
解析
- [ 30 ] The skeletal structure of circumcircumcircumcoronene, a hydrocarbon with the chemical formula C H , is shown below. 150 30 Each line segment between two atoms is at least a single bond. However, since each carbon (C) requires exactly four bonds connected to it and each hydrogen (H) requires exactly one bond, some of the line segments are actually double bonds. How many arrangements of single/double bonds are there such that the above requirements are satisfied? If the correct answer is C and your answer is A , you get (⌊ ( ∣ ∣ )⌋ ) ∣ ∣ A max 30 1 − log , 0 points. ∣ ∣ log C C 2 Proposed by: Yuan Yao Answer: 267227532 The problem is equivalent to the one in OEIS A008793, a.k.a. ”number of ways to tile hexagon of edge n with diamonds of side 1.” Notice that there is a bjiection between such a tiling and the number of ways to stack some unit cubes alongside a corner of an n × n × n box (see the Art of Problem Solving logo as an example, also known as 3-dimensional Young diagrams), where this problem n = 5. It is ( ) 2 n known that there are = 252 ways to stack one layer (since each way correspond a way to walk from n 5 252 9 a corner of a 5 by 5 grid to the opposite one), so ≈ 8 × 10 gives a somewhat loose upper bound 5! (generate five layers and sort them by size, and hope that it will be a valid stack in general). This result can be improved by dividing out a reasonable constant factor after considering the probability that sorting by size indeed gives a valid stack (for example, it would be fair to guess that there is about 1 a chance that the first row of each layer will be in the right order, given that each row has a small 4! role in determining the final size of the layer; dividing 24 from the previous result gives a very close 8 9 guess). In general, a guess anywhere between 10 and 10 is a fair guess.