実践演習 整数系

不定方程式の難良問【2007年度 京都大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)

与えられた \(p\) という文字を使ってよい中で、条件を満たす整数 \(a\) ,  \(b\) ,  \(c\) ,  \(d\) を求めるという不定方程式の問題です。

  • 試行錯誤的にやってみたら解けた
  • 戦略をもって見通しをもちながら解けた
  • そもそも手も足もでなかった

という3タイプに分かれると思います。

試験場においては、解けたもん勝ちという側面が強いですが、普段の学習においては爪がひっかかる部分をどのように見出していくか目を光らせる訓練を積むことが大切です。

本問は、一見どこから崩せばよいのか見当がつきにくいと思います。

試験場で手掛かりとなるのは問題文だけです。

問題文から、何を感じ取れるかということを意識して取り組んでみてほしいと思います。

したがって、答えをすぐに見てしまうと効果半減というタイプの問題です。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

問題を整理する

未知数を \(a\) ,  \(b\) ,  \(c\) ,  \(d\) と見なせば、

$$\begin{eqnarray}
\left\{
\begin{array}{l}
a+b+c+d = 0 \\
ad-bc = -p\\
a \geq b \geq c \geq d
\end{array}
\right.
\end{eqnarray}$$

という形で、 \(a\) ,  \(b\) ,  \(c\) ,  \(d\) を中心に整理したくなります。

この未知数 \(a\) ,  \(b\) ,  \(c\) ,  \(d\) に対して、等式は 2 本しかありません。

つまり、文字の個数に対して、等式の本数が足りない不定方程式の問題ということになります。

問題を見て思うこと

整数問題の基本は

整数問題の有力方針

  • 積の形から約数の拾い上げ
  • 余りで分類
  • 評価する(範囲を絞る)

という3つの方針です。

素数 \(p\) の活かし方

素数の扱いとしては

  • \(p=2\) 以外の素数は奇数であること
  • 素数の約数は \(1\) と自分自身であり、素数の約数は拾いきれるということ

が特徴であり、これらが問題を解く中で効いてくることを身構えておきます。

そうなってくると、

  • 積の形からの約数の拾い上げ

を狙っていくことを考えていきたくなるでしょう。

偶奇については、与えられた等式から今すぐ何かがパッと言えるわけではなさそうですが、条件でわざわざ

「 \(p\) が奇素数である」

と言っているぐらいですから、どこかで奇数ということが効いてくることは意識しておきたいところです。

大小関係について

与えられた

\(a \geq b \geq c \geq d\)

という大小関係から、恐らく整数問題の有力方針の1つである

  • 評価する(範囲を絞る)

ということもどこかで利用することが考えられます。

ただ、今回は「負の整数」もあり得るため、最初に与えられた等式に対して不等式を繋ぎ評価するということをしても、あまり効果がなさそうです。

これも、解き進めていくうちに効いてくるのかなと、一旦保留しておきます。

路線1:対称式を活かす

問題を見て、身構えておくべきことを整理した段階で、いよいよ切り崩しに入ります。

自分が最初に目に付いたのは、与えられた等式が

和の形と積の形

という部分です。

そこで、その対称式を活かすべく、与えられた等式を

$$\begin{eqnarray}
\left\{
\begin{array}{l}
a+d = -(b+c) \\
ad = bc-p
\end{array}
\right.
\end{eqnarray}$$

と見て、

解と係数の関係

\(X\) についての2次方程式

\(X^{2}+(b+c)X+bc-p=0\)

の解が \(a\) ,  \(d\) である。

と処理しようと思いました。

\(X=a\) が解であるため

\(a^{2}+(b+c)a+bc-p=0\)

ということになります。

積の形を作ろうということは身構えていましたので、これが

\((a+b)(a+c)=p\)

という形に変形できるということも、狙っていればスムーズに見抜けるでしょう。

この後は目論見通り、素数の約数が拾いきれることを活かしていきます。

路線2:1文字消去

基本

条件1つで1文字消去

という基本にしたがって、

\(d=-(a+b+c)\)

などと、1文字消去することも考えられます。

これを \(ad-bc+p=0\) に代入すると

\(-a(a+b+c)-bc+p=0\)

\(a(a+b+c)+bc=p\)

\(a^{2}+(b+c)a+bc=p\)

\((a+b)(a+c)=p\)

と先ほどの路線1に合流します。

ただ、正直、自分が一番最初に解いたときは

  • 対称性が崩れるなぁ
  • 1文字消去しても何か「焼け石に水」感が強いなぁ

という直感的な部分で敬遠してしまいました。

この後の処理

\(a+b \geq a+c \geq d+c=-(a+b)\)

ということに注意すれば

  • \(a+b \geq 0\)
  • \(a+b \geq a+c\)

であることから、

\((a+b)(a+c)=p\)

を満たすとき、

$$\begin{eqnarray}
\left\{
\begin{array}{l}
a+b = p \\
a+c = 1
\end{array}
\right.
\end{eqnarray}$$

という形に限られることになります。

ここから、

$$\begin{eqnarray}
\left\{
\begin{array}{l}
b = p-a \\
c = 1-a\\
d=-a-b-c=a-p-1
\end{array}
\right.
\end{eqnarray}$$

と、\(b\) ,  \(c\) ,  \(d\) が全て \(a\) を用いて表せます。

ここで、使い方の分からなかった大小関係にぶち込むと

\(a \geq p-a \geq 1-a \geq a-p-1\)

となり、これを整理すると

\(1 \leq p \leq 2a \leq p+2\)

を得ます。

そうなると、ここでも最初に身構えていた

\(p\) が奇数

という部分が効いてきて

連続する奇数 \(p\) ,  \(p+2\) の間に偶数である \(2a\) がいる

ということになり、

\(2a=p+1\)

となるしか逃げ道がありません。

これにより

\(a=\displaystyle \frac{p+1}{2}\)

と \(a\) を得て、\(b\) ,  \(c\) ,  \(d\) が全て \(a\) を用いて表せていることから、解決します。

解答はコチラ

-実践演習, 整数系
-

© 2022 MathClinic