My Brain is Open.

思いついたことを適当に列列と

数学夏祭りNo.1 (8/31) の解説

数学

問題

こちらの問題を解説していきます。

解説

$1/p + 1/q = r/79$ について $1 \leq r < 79$ より、$1/79 \leq 1/p + 1/q < 1$ 。また $p \leq q$ より $1/q \leq 1/p$ となるため

\[ \frac{1}{79} \leq \frac{1}{p} + \frac{1}{q} \leq \frac{1}{p} + \frac{1}{p} = \frac{2}{p} \]

となり $p$ は最大でも $2\times 79 = 158$ となる。また、$p=1$ のとき$1/p = 1$ のため、条件を満たす $q,r$ は存在しない。 したがって、 $2 \leq p \leq 158$ となる。

両辺を $79pq$ 倍すると

\[ 79(p+q) = pqr \]

を得るが、 $79$ は素数かつ $r < 79$ であるため、「 $p$ が $79$ の倍数」または「 $q$ が $79$ の倍数」である。

場合1: $p$ が $79$ の倍数

$p$ が $79$ の倍数のとき、前述の $p$ の条件より $p = 79, 158$ に限られる。

$p=79$ のとき

\[ \frac{1}{q} = \frac{r-1}{79}　\Leftrightarrow q = \frac{79}{r-1} \]

において $79$ は素数なので $q=79, r=2$ のみ。

$p=158$ のとき

\[ \frac{1}{q} = \frac{2r-1}{158}　\Leftrightarrow q = \frac{158}{2r-1} \]

において、 $(p=)158 \leq q$ より $q=158, r=1$ のみ。

場合2: $q$ が $79$ の倍数

$q=79n$ $(n=1,2,3,\dots)$ とする。このとき

\[ \frac{1}{p} + \frac{1}{79n} = \frac{79n + p}{79np} = \frac{r}{79} \]

より

\[ \frac{79n + p}{np} = r \]

を得る。 $r$ は整数なので $79n+p$ が $np$ で割り切れる場合に限られる。

このとき、$p \geq 2$ より $79n$ が $p$ で割り切れるため、（すでに $p$ が $79$ の倍数の場合は調べたので） $p$ が $79$ の倍数でない場合は、 $n=p$ の場合のみ。 したがって、

\[ \frac{79p + p}{p^2} = \frac{80p}{p^2} = \frac{80}{p} = r \]

となり $p$ は $80$ の約数であればよく、 $(p,q,r)$ の組み合わせは以下の通り。

\[ (2,158,40), (4,316,20), (5,395,16), (8,632,10), (10,790,8), (16,1264,5), (20,1580,4), (40,3160,2), (80,6320,1) \]

まとめ

以上を $p$ の小さい順に並べると次のようになる

$p$ $q$ $r$
2 158 40
4 316 20
5 395 16
8 632 10
10 790 8
16 1264 5
20 1580 4
40 3160 2
79 79 2
80 6320 1
158 158 1

問にある「前から $3$ 番目の $r$ 」は $16$ 、 「後ろから $5$ 番目にある $q$ 」は $1580$ のため、回答は $16 \times 1580 = 25280$ となる。

おまけ： Ruby による総当り計算のワンライナー

あくまで検算用として総当りで調べる方法も書いておく。ただし、いきなり p,q,r を任意の整数にして探すより、上記の解説のように $p$ の取りうる範囲を絞ったりして有限の組み合わせから探すようにしたほうが効率がよい。

$ ruby -e '2.upto(158) { |p_| 78.downto(1) { |r| q_inv = Rational(r,79) - Rational(1,p_); break if q_inv <= 0; q = 1/q_inv; puts "p = #{p_}, q = #{q.to_i}, r = #{r}" if q.denominator == 1 and p_ <= q }}'

フォーマットするとこんな感じ。

2.upto(158) { |p_|
  78.downto(1) { |r|
    q_inv = Rational(r,79) - Rational(1,p_)
    break if q_inv <= 0
    q = 1/q_inv
    puts "p = #{p_}, q = #{q.to_i}, r = #{r}" if q.denominator == 1 and p_ <= q
  }
}

\[ \frac{1}{q} = \frac{r}{79} - \frac{1}{p} \]

を計算して $q$ が正の整数かつ $p \leq q$ となる組み合わせを列挙する。