JOI 2007 本戦 E - 最軽量のモビール

• 問題
• AC

モビールは二分木とみなせるので、部分モビール（=部分木）や子モビールなど、木に類似した言葉を使うことにする。また、おもりも1頂点のみのモビールとみなす。

補題: 部分モビール$M$が与えられたとし、$M$の比を$p:q$とする。また、$a, b \in {\mathbb N}$が与えられたとし、$M$の左の子モビールが成立する重さの集合が$a$の正の倍数の集合であり、右の子モビールが成立する重さの集合が$b$の正の倍数の集合であるとする。このとき、$M$が成立する重さの集合は$ab(p+q)/\gcd(ap, bq)$の正の倍数の集合である。

証明: 与えられた条件より、$M$が成立するのは$k, l \in {\mathbb N}$が存在して$p\cdot ak = q \cdot bl$が成り立つときであり、またその時に限る。一次不定方程式の一般解を考えると、$s \in {\mathbb N}$が存在して$k, l$は

$k = \frac{bq}{\gcd(ap, bq)}s, \ l = \frac{ap}{\gcd(ap, bq)}s$

と表され、$M$の重さは

$ak + bl = \frac{ab(p+q)}{\gcd(ap, bq)} s$

となる。逆に、$ab(p+q)/\gcd(ap, bq)$の倍数であるような重さに対しては、$k, l$を上のように定めれば$p\cdot ak = q \cdot bl$が成り立ってモビールが成立する。□

末端、つまりおもりに関する条件は「$1$の倍数であること」なので、補題より再帰的にモビール全体が成立する重さが求まることになる。