方程式1/a+1/b=p/10
最近数カ月ぶりに Project Euler の問題を解いていると,面白い問題があったのでその例題を紹介します.実際の Project Euler の問題については別の記事で書くことにします.
問題.
問題自体は非常にシンプルです.
少し話はそれますが,これと似た次のような問題なら見たことがあるかもしれません.
こちらの問題は高校でも習うかと思うので,一般的な解き方を紹介しておきます.
まず,不等式を使って調べる範囲を絞っていきます.
よりなので,が得られます.
さらに, より なので,
となり, より,が得られます.
よって,はをみたすので,またはです.
の値を方程式に代入してを求めれば,この方程式の解は の2つであるとわかります.
さて,もとの問題に戻りましょう.
(1)式では,右辺にもという変数があるので,先程の問題のように不等式で範囲を絞る方法が取れません.そこで,少し特殊な変形をして解いていきます.
解き方.
まず,方程式の両辺にをかけて分母を払い,式を整理してみましょう.
\begin{align*}
\frac{1}{a}+\frac{1}{b} &= \frac{p}{10}\\
10b + 10a &= pab\\
pab-10a-10b&= 0
\end{align*}
ここで少し特殊なことをするのですが,両辺にをかけます.
さらに,左辺が因数分解できるように,両辺に100を足します.
このように,左辺は因数分解された形,右辺は文字を含まない整数だけ,という形に変形することができます.一般的に,整数解を求める問題ではこのような変形が有効となる場合がしばしばあります.
この変形の何が嬉しいかというと,左辺のはそれぞれ整数ですが,その積がなので,よりであることも考慮すると,
と絞ることができます.よって,
はの公約数なので,これを満たすの組は,
\begin{align*}
(a, b, p) &= (110, 11, 1), (10, 1, 11),\\
& (60, 12, 1), (30, 6, 2), (20, 4, 3), (15, 3, 4), (10, 2, 6), (5, 1, 12),\\
& (35, 14, 1), (5, 2, 7),\\
& (30, 15, 1), (10, 5, 3), (6, 3, 5), (2, 1, 15),\\
& (20, 20, 1), (10, 10, 2), (5, 5, 4), (4, 4, 5), (2, 2, 10), (1, 1, 20)
\end{align*}
の20個となります.