方程式 1/a+1/b=p/10

この記事の所要時間: 418

方程式1/a+1/b=p/10

最近数カ月ぶりに Project Euler の問題を解いていると,面白い問題があったのでその例題を紹介します.

実際の Project Euler の問題については別の記事で書くことにします.

問題.

方程式\begin{align}\frac{1}{a}+\frac{1}{b}=\frac{p}{10}\tag{1}\end{align}を満たす自然数\((a, b, p)\)の組(\(a\geqq b\))はいくつあるか.

問題自体は非常にシンプルです.


少し話はそれますが,これと似た次のような問題なら見たことがあるかもしれません.

方程式\[\frac{1}{a}+\frac{1}{b}=\frac{1}{2}\]を満たす自然数\((a, b)\)の組(\(a\geqq b\))はいくつあるか.

こちらの問題は高校でも習うかと思うので,一般的な解き方を紹介しておきます.

まず,不等式を使って調べる範囲を絞っていきます.

\(\frac{1}{a}>0\)より\(\frac{1}{b}<\frac{1}{2}\)なので,\(b>2\)が得られます.

さらに,\(a\geqq b\) より \(\frac{1}{a}\leqq \frac{1}{b}\)なので,\[\frac{1}{a}+\frac{1}{b}\leqq \frac{2}{b}\]

となり,\(\frac{1}{2}\leqq \frac{2}{b}\) より,\(b\leqq 4\)が得られます.

よって,\(b\)は\(2<b\leqq 4\)をみたすので,\(b=3\)または\(b=4\)です.

\(b\)の値を方程式に代入して\(a\)を求めれば,この方程式の解は\[(a, b)=(6, 3), (4, 4)\]の2つであるとわかります.


さて,もとの問題に戻りましょう.

(1)式では,右辺にも\(p\)という変数があるので,先程の問題のように不等式で範囲を絞る方法が取れません.そこで,少し特殊な変形をして解いていきます.

解き方.

まず,方程式の両辺に\(10ab\)をかけて分母を払い,式を整理してみましょう.

\begin{align*}
\frac{1}{a}+\frac{1}{b} &= \frac{p}{10}\\
10b + 10a &= pab\\
pab-10a-10b&=0
\end{align*}

ここで少し特殊なことをするのですが,両辺に\(p\)をかけます.さらに,左辺が因数分解できるように,両辺に100を足します.

\begin{align*}
p^2ab-10ap-10bp &= 0\\
p^2ab-10ap-10bp+100 &= 100\\
(pa-10)(pb-10) &= 100
\end{align*}

このように,左辺は因数分解された形,右辺は文字を含まない整数だけ,という形に変形することができます.一般的に,整数解を求める問題ではこのような変形が有効となる場合がしばしばあります.

この変形の何が嬉しいかというと,左辺の\(pa-10, pb-10\)はそれぞれ整数ですが,その積が\(100\)なので,\(a\geqq b\)より\(pa-10\geqq pb-10>-10\)であることも考慮すると,

\begin{align*}
(pa-10, pb-10) &= (100, 1), (50, 2), (25, 4), (20, 5), (10, 10)
\end{align*}

となります.よって,

\begin{align*}
(pa, pb) &= (110, 11), (60, 12), (35, 14), (30, 15), (20, 20)
\end{align*}

\(p\)は\(pa, pb\)の公約数なので,これを満たす\((a, b, p)\)の組は,

\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個となります.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加