2023日本数学オリンピック予選問題の中でプログラミングの練習問題にしたら面白そうな問題
はじめに
毎年、日本数学オリンピックの予選問題を趣味で解いています。その中で、プログラミングの練習問題にしたら面白いかなと思った2023年の問題を紹介します。
問題１
（問題文）
10 を足しても 10 を掛けても平方数となるような最小の正の整数を求めよ。
（Pythonコード）
愚直に 1 から順に試していくだけ。
while の練習に良いかな。
i = 1
while True:
j = (i + 10) ** 0.5
if j == int(j):
k = (i * 10) ** 0.5
if k == int(k):
print(i)
break
i += 1
（数学的解法）
正の整数 $${n}$$ について、$${10n}$$ が平方数となるためには、
$${n=10m^2(m は正の整数)}$$ と表されなければならない。
このとき、$${n+10=10m^2+10=10(m^2+1)}$$ が平方数となるためには、$${m^2+1=10k^2(k は正の整数)}$$ と表されなければならない。
よって、$${m^2=10k^2-1}$$ が平方数となる最小の正の整数 $${k}$$ を求めれば良い。
(2 次関数 $${x^2(x>0)}$$ は単調増加より)
$${k=1 のとき、m^2=10k^2-1=10・1^2-1=9=3^2}$$ となり条件を満たす。
ゆえに、$${n=10m^2=10・9=90}$$
問題２
（問題文）
2 の方が 3 より多く各桁に現れるような正の整数を良い数と呼び、3 の方が 2 より多く各桁に現れるような正の整数を悪い数と呼ぶ。たとえば、2023 には 2 が 2 回、3 が 1 回現れるので、2023 は良い数であり、123 には 2 が 1 回、3 が 1 回現れるので、123 は良い数でも悪い数でもない。
2023 以下の良い数の個数と、2023 以下の悪い数の個数の差を求めよ。
（Pythonコード）
これも 1 から数えていくだけ。
list(str(i)) で、数を各桁に分解してリストにするテクニックの練習になるかも。
ans = 0
for i in range(1, 2024):
s = list(str(i))
n2 = s.count("2")
n3 = s.count("3")
if n2 > n3:
ans += 1
elif n2 < n3:
ans -= 1
print(ans)
if を使わないコード
ans = 0
for i in range(1, 2024):
s = list(str(i))
n2 = s.count("2")
n3 = s.count("3")
ans += (n2 != n3) * (-1) ** (n2 < n3)
print(ans)
（数学的解法）
1999 以下の正の整数において、2 と 3 を入れ替えた整数は 1 対 1 に対応するので、良い数の個数と悪い数の個数の差は 0 となる。
2000 ～ 2023 の 24 個の整数について、2003, 2013 を除いた整数は良い数である。悪い数はない。
よって、$${24-2=22}$$
問題４
（問題文）
正の実数 $${x, y}$$ に対し、正の実数 $${x*y}$$ を $${x*y=\frac{x}{xy+1}}$$ で定める。このとき、
$${(((⋯(((100*99)*98)*97)*⋯)*3)*2)*1}$$
を計算せよ。ただし解答は $${*}$$ を用いず数値で答えること。
（Pythonコード）
まず、$${x*y}$$ の結果がどうなるか（整数なのか分数なのか）考える。
$${x*y=\frac{x}{xy+1} ⋯ (A)}$$
において、$${x, y}$$ を正の整数、$${x, y}$$ の最大公約数を $${gcd(x, y)}$$ と表すことにすると、ユークリッドの互除法より、
$${gcd(x, xy+1)=gcd(x, 1)=1}$$
であるから、$${(A)}$$ の分母、分子は互いに素となり、$${xy+1>1}$$ であるから $${x*y}$$ の結果は既約分数となることが分かった。
そこで、計算の結果を分数で出力するために、分母、分子の漸化式を考える。
$${m, n}$$ を互いに素な正の整数、$${i}$$ を正の整数とすると
$${ \frac{m}{n}*i=\frac{\frac{m}{n}}{\frac{m}{n}×i+1}=\frac{m}{m×i+n} ⋯ (B)}$$
また、
$${gcd(m, m×i+n)=gcd(m, n)=1}$$
であるから、$${(B)}$$ の分母、分子は互いに素となる。
このことから、$${100=\frac{100}{1}}$$として、分子は 100 のまま、分母は $${i}$$ を 99 から 1 まで変化させ計算した結果をそのまま出力すれば良いことが分かる。
m, n = 100, 1
for i in range(1, 100)[::-1]:
n = m * i + n
print(f"{m}/{n}")
数学的すぎるから、練習にならないかも。
（数学的解法）
$${(x*y)*z = \frac{x}{xy+1}*z = \frac{\frac{x}{xy+1}}{\frac{x}{xy+1}×z+1} }$$
$${= \frac{x}{xz+(xy+1)} = \frac{x}{x(y+z)+1} }$$
$${= x*(y+z)}$$
を繰り返し用いると、
$${(((⋯(((100*99)*98)*97)*⋯)*3)*2)*1}$$
$${= 100*(99+98+97+⋯3+2+1) }$$
$${= 100*(\frac{1}{2}・99・(99+1)) }$$
$${= 100*4950}$$
$${= \frac{100}{100×4950+1}}$$
$${= \frac{100}{495001}}$$