$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$ 円である.

　このような直方体において, 底面の隣り合う $2$ 辺の長さを $x,$ $y$ $(x \leqq y)$ とおく. このとき, 底面積は $xy,$ 側面積は $2x+2y$ であるから, \[ xy = 2x+2y\] が成り立つ. これは \[\begin{aligned} xy-2x-2y+4 &= 4 \\ (x-2)(y-2) &= 4 \end{aligned}\] と変形でき, $1 \leqq x \leqq y$ から $-1 \leqq x-2 \leqq y-2$ であるので, \[\begin{aligned} (x-2,y-2) &= (1,4),\ (2,2) \\ (x,y) &= (3,6),\ (4,4) \end{aligned}\] 得られる. ゆえに, 条件を満たす直方体は $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$ である.

　方眼紙の罫線の交点を頂点とする三角形 $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$ の面積は整数である.

　複数個の石が $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$ 個である.

　複数個の球が $x$ 段の正四角錐の形にも, $y$ 行 $y$ 列の正方形の形にも並べられたとする. このとき, が成り立つ.

(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$ 個である.