HMMT 十一月 2017 · 冲刺赛 · 第 35 题

HMMT November 2017 — Guts Round — Problem 35

[ 30 ] Rebecca has twenty-four resistors, each with resistance 1 ohm. Every minute, she chooses any two resistors with resistance of a and b ohms respectively, and combine them into one by one of the following methods: • Connect them in series, which produces a resistor with resistance of a + b ohms; ab • Connect them in parallel, which produces a resistor with resistance of ohms; a + b • Short-circuit one of the two resistors, which produces a resistor with resistance of either a or b ohms. Suppose that after twenty-three minutes, Rebecca has a single resistor with resistance R ohms. How many possible values are there for R ? ∣ ∣ (⌊ ( )⌋ ) ∣ ∣ 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 ] Rebecca has twenty-four resistors, each with resistance 1 ohm. Every minute, she chooses any two resistors with resistance of a and b ohms respectively, and combine them into one by one of the following methods: • Connect them in series, which produces a resistor with resistance of a + b ohms; ab • Connect them in parallel, which produces a resistor with resistance of ohms; a + b • Short-circuit one of the two resistors, which produces a resistor with resistance of either a or b ohms. Suppose that after twenty-three minutes, Rebecca has a single resistor with resistance R ohms. How many possible values are there for R ? 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: 1015080877 This is the same problem as in OEIS A153588. It is helpful to see (or guess) that neither the numerator or the denominator of the final resistance exceed the ( n + 1)-th Fibonacci number, which in this case 2 9 is F = 75025, using concepts on the line of continued fractions. So 75025 ≈ 5 . 6 × 10 is an upper 25 bound for the total number, which is already close to the final answer. Multiplying by some constant 3 factor to remove non-reduced fractions (such as to deal with parity) will improve this result. 4