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 anytwo 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;
• Connect them in parallel, which produces a resistor with resistance of ohms;aba + b
• Short-circuit one of the two resistors, which produces a resistor with resistance of either a or bohms.
Suppose that after twenty-three minutes, Rebecca has a single resistor with resistance R ohms. Howmany possible values are there for R ?
∣ ∣
(⌊ ( )⌋ )
∣ ∣
If the correct answer is C and your answer is A , you get max 30 1 − log , 0 points.A
∣ ∣
log C
2C
解析
英文解析
- [ 30 ] Rebecca has twenty-four resistors, each with resistance 1 ohm. Every minute, she chooses anytwo 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;
• Connect them in parallel, which produces a resistor with resistance of ohms;aba + b
• Short-circuit one of the two resistors, which produces a resistor with resistance of either a or bohms.
Suppose that after twenty-three minutes, Rebecca has a single resistor with resistance R ohms. Howmany possible values are there for R ? If the correct answer is C and your answer is A , you get
∣ ∣
(⌊ ( )⌋ )
∣ ∣
max 30 1 − log , 0 points.A
∣ ∣
log C
2C
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 numeratoror 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 upperbound for the total number, which is already close to the final answer. Multiplying by some constant 25
factor to remove non-reduced fractions (such as to deal with parity) will improve this result.3 4