有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

本格数学クイズ (整数論)

不定方程式

クイズ《フロベニウスの硬貨交換問題》

 $a,$ $b$ を互いに素な $1$ より大きい整数とする. $a$ 円硬貨, $b$ 円硬貨のみを使ってちょうど支払えない金額は最大で何円か. ただし, 各硬貨は何枚使ってもよいが, おつりはもらえないものとする.
(有名問題)
$2023/07/07$$2023/07/13$

答え

 $ab-a-b$ 円.

解説

 $c$ 円が $a$ 円硬貨, $b$ 円硬貨のみを使って支払えるとき, \[ ax+by = c \quad \cdots [\ast ]\] は非負の整数解をもつ. よって, $[\ast ]$ が非負の整数解をもたないような正の整数 $c$ の最大値を求めればよい. 例えば, $a,$ $b$ $(a < b)$ が $1$ 桁の素数であるとき, そのような $c$ の値は, \[ c = \begin{cases} 1 & (a = 2,\ b = 3), \\ 3 & (a = 2,\ b = 5), \\ 5 & (a = 2,\ b = 7), \\ 7 & (a = 3,\ b = 5), \\ 11 & (a = 3,\ b = 7), \\ 23 & (a = 5,\ b = 7) \end{cases}\] である. これらの数値から求める金額は $ab-a-b$ 円であると推測できるので, そのことを証明する.
(1)
$c = ab-a-b$ のとき $[\ast ]$ は非負の整数解をもたないことを示す. 整数 $x,$ $y$ が \[ ax+by = ab-a-b \quad \cdots [1]\] つまり \[ a(x+1)+b(y+1) = ab \quad \cdots [2]\] を満たすとする. \[ a(x+1) = b(a-y-1), \quad a(b-x-1) = b(y+1)\] であり, $a,$ $b$ は互いに素であるから, $x+1$ は $b$ の倍数, $y+1$ は $a$ の倍数である. $[2]$ の左辺が $ab$ を超える $ab$ の倍数になることはないから, $x,$ $y \geqq 0$ となることはない. ゆえに, $[1]$ は非負の整数解をもたない.
(2)
$c \geqq ab-a-b+1$ のとき, $[\ast ]$ は非負の整数解をもつことを示す. $a,$ $b$ は互いに素であるから, \[ ax+by = c \quad \cdots [3]\] は整数解 $(x,y) = (x_0,y_0)$ をもつ. $x_0$ を $b$ で割った商 $q$ について $(x,y) = (x_0-bq,y_0+aq)$ も $[3]$ の整数解であるから, $0 \leqq x \leqq b-1$ なる整数解が存在する. このような $[3]$ の整数解 $(x,y)$ について, \[ y = \frac{c-ax}{b} \geqq \frac{ab-a-b+1-a(b-1)}{b} = \frac{1}{b}-1 > -1\] であるから, $y \geqq 0$ も成り立つ. ゆえに, $[3]$ は非負の整数解をもつ.
(1), (2) から, $a$ 円硬貨, $b$ 円硬貨のみを使ってちょうど支払えない金額は最大で $ab-a-b$ 円である.

参考

 $a_1,$ $\cdots,$ $a_n$ を互いに素な正の整数とする.
  • $a_1$ 円硬貨 (切手), $\cdots,$ $a_n$ 円硬貨 (切手) のみを使ってちょうど支払えない金額 (郵便料金) の最大値を求める問題を「フロベニウスの硬貨交換問題」(coin-exchange problem of Frobenius) または「シルヴェスターの切手問題」(Sylvester's postage stamp problem) と呼び, その最大値を整数の組 $\{ a_1,\cdots,a_n\}$ の「フロベニウス数」(Frobenius number) と呼ぶ.
  • $n \geqq 3$ のとき,「フロベニウス数」を求める明示的な公式は発見されていない. $n = 3$ のとき,「フロベニウス数」の上限, 下限が得られており,「フロベニウス数」を求める高速なアルゴリズムも発見されている.
  • $a_1$ 円硬貨 (切手), $a_2$ 円硬貨 (切手) のみを使ってちょうど支払えない金額 (郵便料金) は $\dfrac{(a_1-1)(a_2-1)}{2}$ 通りであることが, シルヴェスターによって示されている.

クイズ《底面積と側面積が等しい整数直方体》

 高さが整数 $z$ であり, 残りの辺の長さも整数であって, 底面積と側面積が等しい直方体は何個あるか.
(オリジナル)
$2023/10/20$$2023/12/11$

答え

 $z$ が $z = 2^{e_0}p_1{}^{e_1}\cdots p_r{}^{e_r}$ ($e_0$: 非負整数, $p_k$: 相異なる $3$ 以上の素数, $e_r$: 正の整数) と素因数分解されるとき,
$\dfrac{(2e_0+3)(2e_1+1)\cdots (2e_r+1)+1}{2}$ 個.

解説

 このような直方体において, 横の長さを $x,$ 縦の長さを $y$ とおく. 底面積は $xy,$ 側面積は $2xz+2yz$ であるから, \[ xy = 2xz+2yz\] が成り立つ. この方程式は \[\begin{aligned} xy-2xz-2yz+4z^2 &= 4z^2 \\ (x-2z)(y-2z) &= 4z^2 \end{aligned}\] と変形できる. よって, 整数の組 $(x-2z,y-2z)$ は $4z^2$ の正の約数と $1$ 対 $1$ に対応する. したがって, 整数の組 $(x,y)$ も $4z^2$ の正の約数と $1$ 対 $1$ に対応する. $4z^2$ は平方数であるから, その正の約数の個数 $N$ は奇数であり, $x = y = 4z$ のときに限り $x,$ $y$ の値は一致する. また, 横の長さと縦の長さを入れ替えた直方体も同じ直方体であるから, 条件を満たす直方体の個数は
$\dfrac{N-1}{2}+1 = \dfrac{N+1}{2}$ (個)
である. ここで, $z$ が
$z = 2^{e_0}p_1{}^{e_1}\cdots p_r{}^{e_r}$
  ($e_0$: 非負整数, $p_k$: 相異なる $3$ 以上の素数, $e_r$: 正の整数)
と素因数分解されるとき, \[ 4z^2 = 2^{e_0+2}p_1{}^{2e_1}\cdots p_r{}^{2e_r}\] であり, 約数の和の公式により \[ N = (2e_0+3)(2e_1+1)\cdots (2e_r+1)\] であるから, 求める個数は
$\dfrac{(2e_0+3)(2e_1+1)\cdots (2e_r+1)+1}{2}$ 個
である.

参考

  • $z = 1$ のとき, 上記のような直方体は $2$ 個ある.
  • 周の長さと面積が等しい図形を「等長積図形」と呼ぶ (equable shape の和訳として提案したい). $z = 1$ のときの直方体の底面は「等長積長方形」である.

クイズ《ピタゴラスの $3$ つ組に現れる整数》

 同じ長さのマッチ棒をつなげて直角三角形の枠を作るとき, $1$ 辺に使われるマッチ棒の本数として考えられない整数の最大値はいくらか.
(オリジナル)
$2023/10/27$$2023/10/27$

答え

 $2.$

解説

 各辺のマッチ棒の本数を $a,$ $b,$ $c$ とおく. 三平方の定理により \[ a^2+b^2 = c^2 \quad (a,\ b,\ c > 0) \quad \cdots [\ast ]\] が成り立つ.
(i)
まず, $a = 2$ または $b = 2$ または $c = 2$ であるとき, $[\ast ]$ が成り立たないことを示す. \[ (c+b)(c-b) = c^2-b^2 = 2^2 \quad (b,\ c \geqq 0)\] の整数解は $c+b = c-b = 2$ から $(b,c) = (0,2)$ に限るので ($c+b = 4,$ $c-b = 1$ なら $c = \dfrac{5}{2}$ となってしまう), $a = 2$ のとき $[\ast ]$ は成り立たない. 同様に, $b = 2$ のときも $[\ast ]$ は成り立たない. また, \[ a^2+b^2 = 2^2 \quad (a,\ b \geqq 0)\] の整数解は $a,$ $b \in \{ 0,1,2\}$ から $(a,b) = (2,0),\ (0,2)$ に限るので, $c = 2$ のとき $[\ast ]$ は成り立たない.
(ii)
$a$ が奇数で $a \geqq 3$ であるとき. $a^2$ は $9$ 以上の奇数で $a^2\pm 1$ は正の偶数, よって $\dfrac{a^2\pm 1}{2}$ は正の整数であり, \[\begin{aligned} &\left(\frac{a^2+1}{2}\right) ^2-\left(\frac{a^2-1}{2}\right) ^2 \\ &= \frac{(a^4+2a^2+1)-(a^4-2a^2+1)}{4} = \frac{4a^2}{4} = a^2 \end{aligned}\] から \[ a^2+\left(\frac{a^2-1}{2}\right) ^2 = \left(\frac{a^2+1}{2}\right) ^2\] が成り立つので, $b = \dfrac{a^2-1}{2},$ $c = \dfrac{a^2+1}{2}$ とおけば $[\ast ]$ を満たす整数 $b,$ $c$ が得られる.
(iii)
$a$ が $4$ の倍数であるとき. $a$ は $a = 2^ea'$ ($e$: $2$ 以上の整数, $a'$: 正の奇数) と表せる.
  • $a' = 1$ のとき, \[ 4^2+3^2 = 5^2\] であるから, $b = 2^{e-2}\cdot 3,$ $c = 2^{e-2}\cdot 5$ とおけば $[\ast ]$ を満たす整数 $b,$ $c$ が得られる.
  • $a' \geqq 3$ のとき. (ii) により \[ a'^2+b'^2 = c'^2\] を満たす正の整数 $b',$ $c'$ が存在する. よって, $b = 2^eb',$ $c = 2^ec'$ とおけば $[\ast ]$ を満たす整数 $b,$ $c$ が得られる.
(iv)
$a$ を $4$ で割った余りが $2$ で $a \geqq 6$ であるとき. $a' = \dfrac{a}{2}$ は $3$ 以上の奇数であるから, (ii) により \[ a'^2+b'^2 = c'^2\] を満たす正の整数 $b',$ $c'$ が存在する. よって, $b = 2b',$ $c = 2c'$ とおけば $[\ast ]$ を満たす整数 $b,$ $c$ が得られる.
(i)~(iv) から, $1$ 辺に使われるマッチ棒の本数として考えられない整数の最大値は $2$ である.

クイズ《辺長が整数である格子三角形の面積》

 方眼紙の罫線 (間隔は $1$) の交点を頂点とする三角形において, 各辺の長さが整数であるならば面積も整数である, という主張は正しいか. 正しければ証明し, 正しくなければ反例を挙げよ.
(オリジナル)
$2023/11/17$$2023/11/18$

答え

 正しい (証明は解説を参照).

解説

 方眼紙の罫線の交点を頂点とする三角形 $T$ において, $3$ 辺の長さ $a,$ $b,$ $c$ ($a < c,$ $b < c$) が整数であるとする.
(i)
$T$ の $2$ 辺が方眼の罫線上にあるとき. $T$ は各辺の長さが整数の直角三角形である (このような三角形を「ピタゴラスの三角形」と呼ぶ). ここで, 直角を挟む $2$ 辺の長さ $a,$ $b$ の少なくとも一方は偶数である. 実際, 三平方の定理により \[ a^2+b^2 = c^2\] が成り立ち, 偶数 $2n$ の $2$ 乗 $4n^2$ を $4$ で割った余りは $0,$ 奇数 $2n+1$ の $2$ 乗 $4n(n+1)+1$ を $4$ で割った余りは $1$ であるから, $a$ も $b$ も奇数であるとすると $c^2$ を $4$ で割った余りは $2$ になって $c$ は偶数にも奇数にもならないという矛盾が起こるからである. よって, $T$ の面積 $\dfrac{ab}{2}$ は整数である.
(ii)
$T$ の $2$ 辺が方眼の罫線上にないとき. $T$ は, $4$ 辺が方眼の罫線上にある長方形の $2$ つまたは $3$ つの角 (かど) から「ピタゴラスの三角形」を取り除いて得られる. 長方形の面積は整数であり, (i) により取り除く三角形の面積も整数であるから, $T$ の面積も整数である.
(i), (ii) から, $T$ の面積は整数である.

参考

  • $xy$ 平面上の $x$ 座標, $y$ 座標が整数である点を「格子点」(lattice point) と呼び, 各頂点が格子点であるような多角形を「格子多角形」(lattice polygon) と呼ぶ.
  • $3$ 辺の長さが整数である三角形を「整数三角形」(integer triangle) と呼び, $3$ 辺の長さと面積が整数である三角形を「ヘロンの三角形」(Heronian triangle) と呼ぶ.
  • 本問で示したことにより,「整数三角形」のうち,「格子三角形」である三角形は「ヘロンの三角形」である. 逆に,「ヘロンの三角形」は「格子三角形」として描けることが知られている.

クイズ《平方三角数》

 正方形 (中実方陣) の形に並べられた複数個の石を, $1$ 段目に $1$ 個, $\cdots,$ $k$ 段目に $k$ 個, $\cdots$ と並べ直していくと, 正三角形の形に余すことなく並べられた. このとき, 考えられる石の個数として最も少ない個数は何個か.
(有名問題)
$2023/06/23$$2023/06/23$

答え

 $36$ 個.

解説

 複数個の石が $l$ 行 $l$ 列の正方形の形にも, $m$ 段の正三角形の形にも並べられたとする. このとき, $l,$ $m \geqq 2$ と
$l^2 = \displaystyle\sum_{k = 1}^mk$ つまり $l^2 = \dfrac{m(m+1)}{2} \quad \cdots [1]$
が成り立つ. $[1]$ の右辺の $m$ に $2$ 以上の整数を代入していくと, 初めて平方数になる値は $m = 8$ のときの \[\frac{8\cdot 9}{2} = 36\] である. よって, 考えられる石の個数として最も少ない個数は $36$ 個である.

参考

  • 正三角形の形に点を並べたときの点の総数を「三角数」と呼び, 平方数でも「三角数」でもある整数を「平方三角数」と呼ぶ.
  • 「平方三角数」$l^2 = \dfrac{m(m+1)}{2}$ と「ペル方程式」$x^2-2y^2 = 1$ の正の整数解 $(x,y)$ は \[ (x,y) = (2m+1,2l)\] により $1$ 対 $1$ に対応している (こちらを参照). このことと $x^2-2y^2 = 1$ の解の公式 (こちらを参照) を合わせると, 小さい方から $n$ 番目の「平方三角数」は, \[\frac{\{ (3+2\sqrt 2)^n-(3-2\sqrt 2)^n\} ^2}{32}\] と表せることがわかる (L・オイラー, $1778$ 年). 小さい順に「平方三角数」を列記すると, $1,$ $36,$ $1225,$ $41616,$ $1413721,$ $\cdots$ となる.

クイズ《平方四角錐数》

 正方形 (中実方陣) の形に並べられた複数個の球を, $1$ 段目に $1$ 個, $\cdots,$ $k$ 段目に $k$ 個, $\cdots$ となるように積み上げていくと, 正四角錐の形に余すことなく並べられた. このとき, 考えられる球の個数として最も少ない個数は何個か.
(参考:『新しいカギ』「第 $1$ 回高校生クイズ何問目」決勝 $2$ 問目)
$2023/09/15$$2023/09/15$

答え

 $4900$ 個.

解説

 複数個の球が $x$ 段の正四角錐の形にも, $y$ 行 $y$ 列の正方形の形にも並べられたとする. このとき,
$y^2 = \displaystyle\sum_{k = 1}^xk^2$ つまり $y^2= \dfrac{1}{6}x(x+1)(2x+1) \quad \cdots [*]$
が成り立つ.
(1)
$x,$ $x+1,$ $2x+1$ はどの $2$ つも互いに素であることに注意する. 実際, $x+1,$ $2x+1$ を $x$ で割った余りは $1$ であるから, $x$ と $x+1,$ $x$ と $2x+1$ は互いに素である. また, $-(2x+1) = -2(x+1)+1$ を $x+1$ で割った余りは $1$ であるから, $x+1$ と $-(2x+1)$ は互いに素であり, よって $x+1$ と $2x+1$ は互いに素である.
(2)
$5$ 以上の各素数 $p$ に対して, $x,$ $x+1,$ $2x+1$ が $p$ で割り切れる回数はいずれも偶数 ($0$ を含む) であることに注意する. 実際, $[*]$ は \[ 6y^2 = x(x+1)(2x+1)\] と同値である. $5$ 以上の各素数 $p$ に対して, $6y^2$ つまり $x(x+1)(2x+1)$ が $p$ で割り切れる回数は偶数であり, (1) の注意から $x,$ $x+1,$ $2x+1$ のうち高々 $1$ つしか $p$ で割り切れないので, $x,$ $x+1,$ $2x+1$ が $p$ で割り切れる回数はいずれも偶数である.
(3)
最後に, $[*]$ の $(x,y) = (1,1)$ 以外の正の整数解のうち $x$ の値が最小のものを求め, 球の個数を求める. $(x,y)$ を $[*]$ の正の整数解とする. (2) の注意から, $x,$ $x+1,$ $2x+1$ が $5$ 以上の素数で割り切れる回数が奇数になることはない.
  • $x = 5,$ $7,$ $10,$ $11,$ $13,$ $14,$ $15,$ $17,$ $19,$ $20,$ $21,$ $22,$ $23$ は, $x$ が $5$ 以上の素数で割り切れる回数が奇数になることがあるから, 不適.
  • $x = 4,$ $6,$ $9,$ $12,$ $16,$ $18$ は, それぞれ $x+1 = 5,$ $7,$ $10,$ $13,$ $17,$ $19$ が $5$ 以上の素数で割り切れる回数が奇数になることがあるから, 不適.
  • $x = 2,$ $3,$ $8$ は, それぞれ $2x+1 = 5,$ $7,$ $17$ が $5$ 以上の素数であるから, 不適.
  • $\dfrac{1}{6}\cdot 24\cdot 25\cdot (2\cdot 24+1) = 4900 = 70^2$ であるから, $(x,y) = (24,70)$ は $[*]$ を満たす.
ゆえに, $[*]$ の $(x,y) = (1,1)$ 以外の正の整数解のうち $x$ の値が最小のものは $(x,y) = (24,70)$ であり, 求める球の個数は $70^2 = 4900$ 個である.

参考

  • 正の整数 $x,$ $y$ を用いて $N = \dfrac{1}{6}x(x+1)(2x+1) = y^2$ の形に表される正の整数 $N$ は, $x$ 段の正四角錐状にも $y$ 行 $y$ 列の正方形状にも並べられるような球の個数であるから,「平方四角錐数」(square pyramidal number) と呼ばれる. $y^2 = \dfrac{1}{6}x(x+1)(2x+1)$ が $(x,y) = (1,1),$ $(24,70)$ 以外の正の整数解をもつか, つまり「平方四角錐数」が $1,$ $4900$ のみであるかという「リュカのキャノンボール問題」(Lucas' cannonball problem) は, $1918$ 年に肯定的に解決された.
  • $f(x) = 0$ が重解をもたないような $3$ 次多項式 $f(x)$ を用いて $y^2 = f(x)$ で定義される曲線は, 「楕円曲線」(elliptic curve) と呼ばれ, 現代整数論の主要な研究対象である. この形の方程式は有理数係数の場合に高々有限個の整数解しかもたないという「ジーゲルの定理」(Siegel's theorem) が知られている.