#数学夏祭り 問1(8月31日出題)

この記事の所要時間: 545

#数学夏祭り 問1. (8/31出題)

本日8月31日から2週間の間,数学夏祭りというイベントが開催されています.平日に毎日一問ずつ問題がTwitter上で出題され,解答,拡散,解説といった方法で気軽に参加できます.

詳しくは公式サイト(https://mathmatsuri.org)を見てください.

この記事では問1の問題の解説を行います.自分で解きたい方は,その後で見ていただけると良いかと思います.

問題.

問1. \begin{align*}
\dfrac{1}{p} + \dfrac{1}{q} = \dfrac{r}{79}\quad(p \leq q, r<79)
\end{align*}をみたす正整数 \(p, q, r\) の組をすべて求め,\(p\) の小さい順に並べたとき,前から 3 番目の \(r\) と後ろから 5 番目の \(q\) を掛けた数 (\(q\times r\)) を答えよ.

難易度:★★★★☆☆☆☆☆☆

この問題は同じような問題についての記事を以前にも書いたので,そちらも良ければ見てください.

ー>①:方程式 1/a+1/b=p/10

②:Project Euler 157. Solving the Diophantine equation 1/a+1/b=p/10^n

解説

まず,右辺の分子が \(r\) が具体的な整数の場合を考えてみましょう.

例えば,\(r=1\)のとき,

\begin{align*}
\dfrac{1}{p} + \dfrac{1}{q} = \dfrac{1}{79}\quad (p\leq q)
\end{align*}

よくある解法を考えます.
\(p\leq q\) より \(\frac{1}{p}\geq\frac{1}{q}\) なので,

\begin{align*}
\frac{1}{79} &= \frac{1}{p} + \frac{1}{q}\\
&\leq \frac{1}{p} + \frac{1}{p}\\
&= \frac{2}{p}
\end{align*}

となり,\(p\) の取りうる範囲が \(p\leq 2\times 79 =158\) とわかります.
さて,\(p\) は \(1\leq p\leq 158\) なのですべての場合を調べて…としていると候補が多すぎてとても答えにたどり着けません(しかも,\(r\) が \(2, 3, \ldots, 78\) の場合もあります. コンピュータに頼るなら別ですが…).

というわけで,別の方法を考えます.

まず,両辺に \(79pq\) を掛けて分母を払います.

\begin{align*}
79q + 79p = pqr\quad (p\leq q, r<79)
\end{align*}

整数の問題でよく行う方法として,(式)×(式)=(整数)という,左辺は因数分解された形,右辺は整数,の形に変形して解を絞っていく方法があります.そこで,上の式の両辺に \(r\) を掛けて,次のような変形をしていきます.

\begin{align*}
79qr + 79pr &= pqr^2\\
pqr^2 – 79pr – 79qr + 79^2 &= 79^2\\
(pr – 79)(qr-79) &= 79^2
\end{align*}

\(r\) を掛けたことと,両辺に \(79^2\) を足したのは因数分解するためです.
このように変形すると,\(pr-79, qr-79\) は両方とも整数なので,解が絞れていけそうです.

問題の条件から,\(-79<pr-79\leq qr-79\)で,79は素数なので,\((pr-79, qr-79)\)の組は以下の2通りしかありません.

(i) \((pr-79, qr-79) = (1, 79^2)\)

(ii) \((pr-79, qr-79) = (79, 79)\)

(i) のとき,

\(pr = 80, qr = 79^2+79 = 79\times 80\) で,\(r\) は\(80\) と \(79\times80\) の公約数,すなわち\(80\)の約数で,\(r<79\)であることに注意すると,これを満たす \((p, q, r)\) の組は以下になります.

\begin{align*}
(p, q, r) &= (2, 2\times79, 40), (4, 4\times79, 20), (5, 5\times79, 16), (8, 8\times79, 10)\\
&\quad (10, 10\times79, 8), (16, 16\times79, 5), (20, 20\times79, 4), (40, 40\times 79, 2)\\
&\quad (80, 80\times79, 1)
\end{align*}

(ii) のときも同様に調べます.

\(pr = 2\times79, qr = 2\times79\) で,\(r\) は\(2\times 79\)の約数になり,\(r<79\)であることに注意すると,これを満たす \((p, q, r)\) の組は以下になります.

\begin{align*}
(p, q, r) &= (79, 79, 2), (158, 158, 1)
\end{align*}

これですべての解がでたので,\(p\)が小さい順に並べると,

\begin{align*}
(p, q, r) &= (2, 2\times79, 40), (4, 4\times79, 20), (5, 5\times79, 16), (8, 8\times79, 10)\\
&\quad (10, 10\times79, 8), (16, 16\times79, 5), (20, 20\times79, 4), (40, 40\times 79, 2)\\
&\quad (79, 79, 2), (80, 80\times79, 1), (158, 158, 1)
\end{align*}

前から3番目の \(r\) と後ろから5番目の \(q\) の積は,\(16\times20\times79 = 25280\) となります.

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