【数学夏祭り】第一問(整数問題)の解説【2020年夏】

実は、今週から2週間にわたって「数学夏祭り」という数学愛好家向けのイベントがネット上(主にTwitter上)で開催されています!

なんと今回の企画では解説記事も応募対象になっており、しかも第1問は管理人の大好きな整数分野からの出題ということなので、当サイトでも参加してみたいと思います(笑)。25時が解答応募の締め切りということなので、記事の公開は25時ちょうどとしました。

第4問についてはこちらから→【数学夏祭り】第4問(確率)の面白さについて【2020年夏】

第7’問についてはこちらから→【数学夏祭り】第7’問(関数方程式)について【2020年夏】

記念すべき第1問は以下のような問題でした。


【数学夏祭り】第一問


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

(数学夏祭り(2020) 第1問)


《考え方》

方程式の形は入試数学でもよく見かけるタイプです。「$p,q,r$」とあるので一瞬「素数かな?」と思ってしまいますが、「正整数」なのでご注意を。

この問題では、$79$ が素数であることが効いてきます。例えばこれが$$\dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{80}$$とかだと大量の解*1が出てきます。

こういうタイプの問題では、まず$p$や$q$の範囲が絞り込めないか考えましょう。いま $p \leqq q$ なので、$$\dfrac{1}{p} \geqq \dfrac{1}{q}$$となります。これと $r \geqq 1$ より、$$\dfrac{1}{p}+\dfrac{1}{p} \geqq \dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{79} \geqq \dfrac{1}{79}$$ $$\therefore \dfrac{2}{p} \geqq \dfrac{1}{79}$$ $$\therefore \color{red}{p \leqq 79 \times 2}$$と$p$の上限が絞り込めます。

※ $q$についても同様にして $q \geqq 2$ と下限が得られますが、この不等式からは解の個数を絞り込めないので、あまり役に立ちません。$q$について解いて$$\begin{align}
q &= \dfrac{79p}{pr-79} \\ &< \dfrac{79p}{1} \\ &< 79 \times 79 \times 2
\end{align}$$と無理やり上から押さえることもできますが、残念ながら問題を解く上では役に立ちません。

※ $p,\,q$ の上限はたかが知れているので、競プロ経験者とかだとスクリプトを書いて数分足らずで解答してしまった人もいるかもしれません・・・*2

●   ●   ●

ここから先は分数のまま考えても上手くいきませんので、分母を払って考えていきます。与式より、$$79(p+q)=pqr$$という関係式が得られます。ここまでは辿り着けますよね・・・?(笑)

さて、ここからが本題です。左辺に$79$という定数があるので、ここを起点に解を絞り込んできましょう。$79$は素数($\sqrt{79} \ (< 9)$ 未満$2$以上の自然数で$79$を割り切るものは無いので素数だと分かります)であり $r<79$ なので、右辺の$p$、$q$のうち、少なくともいずれか一方は$79$の倍数となります。ここで場合分けが発生しますが、あとは丁寧に調べていくだけなので、ここまで来れば完答が見えてきます!

ただし、勢い余って誤答してしまう前に「$p$の小さい順」というフレーズに十分注意して下さい・・・。詰めが甘いと残念なことになってしまいます。


一応、それっぽい解答を掲載しておきます。解けなかった方は丁寧にフォローしてみて下さい。

解答例

 

$$\begin{cases} \dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{79} & \cdots ① \\ p \leq q & \cdots ② \\ r<79 & \cdots ③ \end{cases}$$とする。$②$より$$\dfrac{1}{p} \geq \dfrac{1}{q}$$が成り立つから、$$\dfrac{1}{p}+\dfrac{1}{p} \geqq \dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{79} \geqq \dfrac{1}{79}$$ $$\therefore \dfrac{2}{p} \geqq \dfrac{1}{79}$$ $$\therefore p \leqq 79 \times 2 \quad \cdots ④$$となる。

 

$①$の分母を払って整理して、$$79(p+q)=pqr \quad \cdots ⑤$$を得る。このとき右辺は$79$の倍数であることが必要であるが、$③$より$r$が$79$の倍数になることはないから、$p$と$q$のいずれか一方が$79$の倍数でなければならない。

 

そこで、以下のように場合分けする。

 

 

ⅰ)$p$が$79$の倍数のとき、$④$より $p=79$ または $p=79 \times 2$ の場合に限られる。

 

$p=79$ のとき$⑤$より、$$79(79+q)=79qr$$ $$\therefore 79+q=qr$$ $$\therefore 79=q(r-1)$$となる。$r-1<79$ より $q=79$、$r=2$ を得る。

 

$p=79 \times 2$ のとき$⑤$を整理すると、$$79 \times 2=q(2r-1)$$となる。$②$より $q \geqq 79 \times 2$ が必要で、このとき $q=79 \times 2$、$r=1$ を得る。

 

以上より、$$\small (p,q,r)=(79,79,2),(79 \times 2,79 \times 2,1)$$は求める解である。

 

 

ⅱ)$q$が$79$の倍数のとき、$q=79m$($m$は正の整数)と置くと$⑤$より、$$79(p+79m)=79mpr$$ $$\therefore p=m(pr-79) \quad \cdots ⑥$$と式変形できる。これより$p$は$m$の倍数となるから、正の整数$k$を用いて $p=mk$ と置ける。これを$⑥$に代入して整理すると$$79=k(mr-1) \quad \cdots ⑦$$を得る。ここで$79$が素数であることに注意すると、$⑦$が成立するとき、

 

a)$(k,mr-1)=(1,79)$

または

b)$(k,mr-1)=(79,1)$

 

が必要である。

 

a)のとき、$k=1$ より $p=m$ となり、$⑦$より$$pr=80 \quad \cdots ⑧$$が必要となる。$⑧$を満たす$m$、すなわち$p$は$③$を考慮すると$$\small m=p=2,4,5,8,10,16,20,40,80$$であり、対応する$q,\,r$は$$q=79p, \ r=\dfrac{80}{p}$$となる。

 

b)のとき、$mr=2$ より $(m,r)=(1,2),(2,1)$ となるが、このとき得られる$p,\,q$の組はⅰ)の場合と同じになる。

 

 

以上ⅰ)ⅱ)より、求める整数 $p,q,r$ の組は$$\small \begin{array}{c|c|c}
p & q & r \\
\hline 2 & 79 \times 2 & 40 \\
4 & 79 \times 4 & 20 \\
5 & 79 \times 5 & \color{red}{\underline{16}} \\
8 & 79 \times 8 & 10 \\
10 & 79 \times 10 & 8 \\
16 & 79 \times 16 & 5 \\
20 & \color{red}{\underline{79 \times 20}} & 4 \\
40 & 79 \times 40 & 2 \\
79 & 79 \times 79 & 2 \\
80 & 79 \times 80 & 1 \\
158 & 79 \times 158 & 1
\end{array}$$ですべてであり、$p$の小さい順に並べたとき、前から$3$番目の$r$と後ろから$5$番目の$q$を掛けた数は、$$\small 16 \times 79 \times 20=\color{red}{25280} \quad \cdots (\text{答})$$と求められる。

 


(コメント)

解答中のポイントとしては、$⑦$のように「定数=因数分解した式」の形になるよう変形するところでしょうか。このようにすることで解の候補が上手く絞り込めます。$p=mk$ のような置き換えも整数問題の定石テクニックですので是非覚えておきましょう。

 

勘の鋭い方なら問題文中の「$p$の小さい順」とか「後ろから$5$番目」などのフレーズから落とし穴の気配を察知できたかもしれませんね。実際に管理人自身も、タイムアタック制だと慌てて数え漏らしたり数え間違えたりする人が結構出てきそうだな~、と思いながら解いてました(笑)。

 

式変形の仕方によっては別のアプローチも考えられます。$$\dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{N}$$という形の方程式は、$$pqr-Np-Nq=0$$と変形できるので両辺に$r$を乗じて$$pqr^2-Npr-Nqr=0$$ $$\therefore (pr-N)(qr-N)=N^2$$と整理できます。原題では $N=79$ なので$$(pr-79)(qr-79)=79^2$$となり、ここから整数組を絞り込むことが可能です。このとき、$$\begin{array}{cc|c}
& pq-79 & qr-79 \\
\hline ① & 1 & 79^2 \\
② & 79 & 79 \\
③ & 79^2 & 1
\end{array}$$となりますが、$pr-N \leqq qr-N$ に注意すると$③$は不適と分かり、$①$もしくは$②$の場合に限られることが分かります。$①$より「$pr=80$ かつ $qr=79 \times 80$」、$②$より「$pr=79 \times 2$ かつ $qr=79 \times 2$」となるので、ここから同様に絞り込みが可能です。もしかするとこちらの方針の方がスッキリ解けるかもしれませんね。

 

その他にも$p$と$q$の最大公約数を設定する方法(こちらも整数問題を解く際の良く知られたテクニックです)など、色々な別解が考えられそうです。

 

お気付きかもしれませんが、解答例中では例えば $79 \times 2$ のようにして細かな計算を頑なに行っていません。$79 \times 2$ の計算結果はもちろん $158$ となりますが、そもそもこの計算は最終的な値を求める上で必要ありません。こういった時間の制約がある問題を解く際は、解答例のように不要な計算に極力時間を割かず、必要最低限の計算コストで解答を仕上げるという時間の節約術が重要です。この姿勢は実際の入試でも大切です。

 

本問に関して、Twitter上では難しかったという声が多いようですが、大学受験数学の知識がすっぽ抜けていなければ難なく完答に漕ぎつけられるレベルの問題だと思います(想定難度も★4つみたいです)。東大京大など難関大を志望している受験生なら20分くらいで片付けたいところですね!*3

 

なお、今回は$79$という素数が登場しましたが、素数$p$に対して $p+1$ が大量に約数を持つもの(例えば$71$や$59$など)を$N$として選べば類題が幾らでも作れます。$$\dfrac{1}{p}+\dfrac{1}{q}=\dfrac{r}{N}$$という方程式を$r$について解いてみると、$$r=\dfrac{N(p+q)}{pq} \quad \cdots (*)$$となるので、もし$N$を合成数としてしまうと$(*)$の右辺の分子を割り切る$p,\,q$の組が大量発生してしまいます。そのため、数十分程度で解けるレベルの問題にするには$N$を素数とするのが好ましいと言えます。

 

それから完全に余談ですが、$N$が素数のとき、$(*)$を満たす$(p,q,r)$の組の個数は、$N+1$ の約数の個数に$1$だけ加えた数に等しくなります。これも証明してみると面白そうです。


 

数学夏祭り」は今回始まったばかりのイベントですが、既に大いに盛り上がっている感があり、数学愛好家としては大変喜ばしい限りです。レッドブル協賛の企画としては、以前「旧帝戦数学部門」というものが開催されたりしていました(第2回に関しては当サイトでも解説しています:第2回「旧帝戦数学部門」を解いてみた)。今回はそれをオンラインでやってみようという試みです。オンライン上だと物理的な制約なしに様々な人が参加できますし、特にTwitter上で盛り上がっていれば、普段数学に親しみのない人でも「なんだなんだ」と寄ってきてくれるかもしれませんからね。いわゆる「日曜数学」の裾野が広がることも期待できそうです。

 

今年は新型コロナウイルスの蔓延により様々なイベントが中止に追い込まれていますが、今回のような企画が少しでも誰かの気晴らしになればと願っています。第2問以降の問題も楽しみですね!

 


*1 同様の問題設定だと、この場合の解は108個存在します。これを手計算ですべて求めさせるのは無慈悲というものでしょう…。

*2 「競プロ」というのは「競技プログラミング」のことです。本問はかなり簡単なスクリプトで処理できてしまいます。例えば今回だとPythonを使えば以下のような10行程度のプログラムを走らせるだけで整数組が全通り求められます。

p = 1
N = 79
while p <= N*2:
    q = p
    while q <= N*N*2:
        r = N*(2*p + q)/(p*q)
        if N*(2*p + q) % (p*q) == 0 and p != 1 and r < N:
            print(p,q,r)
        q = q + 1
    p = p + 1

因みに、高速処理で知られるJuliaを使えば以下のようになります。実際、上記のコードに比べて100倍速いです。

function main()
    N = 79
    times = 0
    for p = 1:N*2
        for q = p:N*N*2
            if N*(2*p + q) % (p*q) == 0 && p != 1 && N*(2*p + q)/(p*q) < N
                println(string(p),", ",string(q),", ",string(N*(2*p + q)/(p*q)))
                times = times + 1
            end
            q = q + 1
        end
    end
end
main()

*3 類題というには程遠いですが、東京工業大学2017年前期第1問なども約数の絞り込みという点では本問と通じるものがあります。こちらも腕試しに丁度良い手頃な問題なのでチャレンジしてみて下さい。

“【数学夏祭り】第一問(整数問題)の解説【2020年夏】” への6件の返信

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です