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

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

問いの花火打ち上がる
世界で一番mathい夏
数学夏祭り
8/31(月) 17:00 第一問 開始#数学夏祭り pic.twitter.com/R5JJPpYF9B

— 数学夏祭り＠8/31 17時開幕 (@mathmatsuri) August 29, 2020

なんと今回の企画では解説記事も応募対象になっており、しかも第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$の小さい順」というフレーズに十分注意して下さい･･･。詰めが甘いと残念なことになってしまいます。

---

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

---

---

*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問なども約数の絞り込みという点では本問と通じるものがあります。こちらも腕試しに丁度良い手頃な問題なのでチャレンジしてみて下さい。