問題 13

問題013｜整数と最大値

難易度 C 目安 45

前半戦

正の整数 $a, b$ に対して， $(2021 a + b) (a + 2021 b)$ は，正の整数 $n$ を用いて $2^{n}$ と表すことができないことを示せ．

$c$ を正の定数とする．実数 $x_{1}, x_{2}, y_{1}, y_{2}$ が

x_{1}^{2} + x_{2}^{2} = y_{1}^{2} + y_{2}^{2} = c^{2}

を満たすとき，

S = (1 - x_{1}) (1 - y_{1}) + (1 - x_{2}) (1 - y_{2})

の最大値を求めよ．

後半戦

正の整数 $a, b, n$ に対して，次の等式を示せ．ただし， $gcd (0, 0) = 0$ と定める．

gcd (n^{a} - 1, n^{b} - 1) = n^{gcd (a, b)} - 1

$k$ を非負整数とする．次の和の値を求めよ．

\sum_{j = 0}^{k} 2^{k - j} (\binom{k + j}{j})

ヒント設問 1

ヒント 1

$2021$ を $3$ で割った余りは $2$ ， $5$ で割った余りは $1$ である．

ヒント 2

与えられた積をそれぞれの法で平方数と関連付け， $2^{n}$ と表せると仮定したときの $n$ の偶奇を調べる．

ヒント設問 2

ヒント 1

$(x_{1}, x_{2}) = (c \cos ϕ, c \sin ϕ)$ ， $(y_{1}, y_{2}) = (c \cos ψ, c \sin ψ)$ とおく．

ヒント 2

三角関数の合成と加法定理で $S$ を整理し，各項が同時に最大となる角を探す．

ヒント設問 3

ヒント 1

$a = q b + r$ と割り算を行うと， $n^{a} - 1$ を $n^{b} - 1$ で割った余りは $n^{r} - 1$ となる．

ヒント 2

指数の組 $(a, b)$ にユークリッドの互除法を適用する．

ヒント設問 4

ヒント 1

和を $S_{k}$ とおき，パスカルの公式を用いて $S_{k - 1}$ と関連付ける．

ヒント 2

別の方法として， $(\binom{k + j}{j}) = (\binom{k + j}{k})$ より，与えられた和を多項式の $x^{k}$ の係数として考える．

解答設問 1

正の整数 $a, b, n$ に対して，

(2021 a + b) (a + 2021 b) = 2^{n}

が成り立つと仮定する．まず， $2021 \equiv - 1 (\mod 3)$ より，

2^{n} \equiv (b - a) (a - b) = - (a - b)^{2} (\mod 3)

である．平方数を $3$ で割った余りは $0$ または $1$ なので，右辺の余りは $0$ または $2$ となる． $2^{n}$ は $3$ の倍数ではないから， $2^{n} \equiv 2 (\mod 3)$ である． $2 \equiv - 1 (\mod 3)$ より， $n$ は奇数でなければならない．

一方， $2021 \equiv 1 (\mod 5)$ より，

2^{n} \equiv (a + b)^{2} (\mod 5)

である．平方数を $5$ で割った余りは $0, 1, 4$ のいずれかであり， $2^{n}$ は $5$ の倍数ではないので，その余りは $1$ または $4$ である．ところが， $n = 2 k + 1$ が奇数ならば，

2^{n} = 2 \cdot 4^{k} \equiv 2 (- 1)^{k} (\mod 5)

となり，余りは $2$ または $3$ である．これは矛盾する．したがって，与えられた積を $2^{n}$ と表すことはできない．

解答設問 2

点 $(x_{1}, x_{2})$ ， $(y_{1}, y_{2})$ は，いずれも原点を中心とする半径 $c$ の円上にある．したがって，実数 $ϕ, ψ$ を用いて，

(x_{1}, x_{2}) = (c \cos ϕ, c \sin ϕ), (y_{1}, y_{2}) = (c \cos ψ, c \sin ψ)

と表せる．これを $S$ に代入して展開すると，

\begin{aligned} S & = 2 - c (\cos ϕ + \sin ϕ + \cos ψ + \sin ψ) \\ + c^{2} (\cos ϕ \cos ψ + \sin ϕ \sin ψ) \\ = 2 - c \sqrt{2} \sin (ϕ + \frac{π}{4}) - c \sqrt{2} \sin (ψ + \frac{π}{4}) + c^{2} \cos (ϕ - ψ) \end{aligned}

となる．正弦と余弦の値は $- 1$ 以上 $1$ 以下であり， $c > 0$ なので，

S \leq 2 + 2 c \sqrt{2} + c^{2} = (c + \sqrt{2})^{2}

を得る．ここで $ϕ = ψ = 5 π / 4$ とすれば，二つの正弦の値はともに $- 1$ ，余弦の値は $1$ となり，等号が成立する．これは，

x_{1} = x_{2} = y_{1} = y_{2} = - \frac{c}{\sqrt{2}}

とすることに対応し，確かに与えられた条件を満たす．よって，求める最大値は

(c + \sqrt{2})^{2}

である．

別解（内積と三角不等式）

ベクトル $u = (1, 1)$ ， $x = (x_{1}, x_{2})$ ， $y = (y_{1}, y_{2})$ を用いると，コーシー・シュワルツの不等式と三角不等式より

S = (u - x) \cdot (u - y) \leq | u - x | | u - y | \leq (\sqrt{2} + c)^{2}

である． $x = y = - (c / \sqrt{2}) u$ とすれば条件を満たし，両方の不等式で等号が成立するので，最大値は $(c + \sqrt{2})^{2}$ である．

解答設問 3

$n = 1$ のときは，約束 $gcd (0, 0) = 0$ により両辺とも $0$ となる．以下， $n \geq 2$ とする．

必要ならば $a, b$ を入れ替え， $a \geq b$ としてよい． $a = q b + r$ （ $q \geq 1, 0 \leq r < b$ ）と表すと，

\begin{aligned} n^{a} - 1 & = n^{r} (n^{q b} - 1) + (n^{r} - 1) \\ = (n^{b} - 1) n^{r} (1 + n^{b} + \dots + n^{(q - 1) b}) + (n^{r} - 1) \end{aligned}

となる． $0 \leq n^{r} - 1 < n^{b} - 1$ なので， $n^{a} - 1$ を $n^{b} - 1$ で割った余りは $n^{r} - 1$ である．したがって，

gcd (n^{a} - 1, n^{b} - 1) = gcd (n^{b} - 1, n^{r} - 1)

が成り立つ．

この操作は，指数の組を $(a, b)$ から $(b, r)$ へ移すユークリッドの互除法に対応している． $d = gcd (a, b)$ とおくと，指数の互除法は有限回で $(d, 0)$ に至るので，上の等式を繰り返すことにより，

\begin{aligned} gcd (n^{a} - 1, n^{b} - 1) & = gcd (n^{d} - 1, n^{0} - 1) \\ = gcd (n^{d} - 1, 0) \\ = n^{d} - 1 \end{aligned}

を得る．よって，題意の等式が成り立つ．

解答設問 4

解法1：漸化式を用いる方法

S_{k} = \sum_{j = 0}^{k} 2^{k - j} (\binom{k + j}{j})

とおく． $S_{0} = 1$ である．以下， $k \geq 1$ とし， $(\binom{m}{- 1}) = 0$ （ $m \geq 0$ ）と定める．パスカルの公式より，

\begin{aligned} S_{k} & = \sum_{j = 0}^{k} 2^{k - j} {(\binom{k - 1 + j}{j}) + (\binom{k - 1 + j}{j - 1})} \\ = 2 S_{k - 1} + (\binom{2 k - 1}{k}) + \sum_{j = 1}^{k} 2^{k - j} (\binom{k - 1 + j}{j - 1}) \\ = 2 S_{k - 1} + (\binom{2 k - 1}{k}) + \sum_{j = 0}^{k - 1} 2^{k - 1 - j} (\binom{k + j}{j}) \end{aligned}

となる．最後の和は， $S_{k}$ の $j = k$ の項を除いて半分にしたものなので，

\sum_{j = 0}^{k - 1} 2^{k - 1 - j} (\binom{k + j}{j}) = \frac{1}{2} {S_{k} - (\binom{2 k}{k})}

である．また， $(\binom{2 k}{k}) = 2 (\binom{2 k - 1}{k})$ より，

S_{k} = 2 S_{k - 1} + \frac{1}{2} S_{k}

を得る．したがって $S_{k} = 4 S_{k - 1}$ であり， $S_{0} = 1$ と合わせると，求める値は

S_{k} = 4^{k}

である．

解法2：係数を比較する方法

$(\binom{k + j}{j}) = (\binom{k + j}{k})$ は $(1 + x)^{k + j}$ の $x^{k}$ の係数である．したがって，求める和は多項式

P_{k} (x) = \sum_{j = 0}^{k} 2^{k - j} (1 + x)^{k + j}

の $x^{k}$ の係数に等しい．等比数列の和の公式を用いると，

\begin{aligned} P_{k} (x) & = 2^{k} (1 + x)^{k} \sum_{j = 0}^{k} {(\frac{1 + x}{2})}^{j} \\ = 2^{k} (1 + x)^{k} \frac{1 - {((1 + x) / 2)}^{k + 1}}{1 - (1 + x) / 2} \\ = \frac{2^{k + 1} (1 + x)^{k} - (1 + x)^{2 k + 1}}{1 - x} \end{aligned}

となる．ここで，形式的べき級数として $1 / (1 - x) = 1 + x + x^{2} + \dots$ と展開する．多項式にこの級数を掛けたときの $x^{k}$ の係数は，その多項式の定数項から $x^{k}$ の項までの係数の和である．よって，求める係数は，

2^{k + 1} \sum_{j = 0}^{k} (\binom{k}{j}) - \sum_{j = 0}^{k} (\binom{2 k + 1}{j})

となる．二項定理より $\sum_{j = 0}^{k} (\binom{k}{j}) = 2^{k}$ である．また， $(\binom{2 k + 1}{j}) = (\binom{2 k + 1}{2 k + 1 - j})$ であり，添字 $0, \dots, k$ と $k + 1, \dots, 2 k + 1$ は一対一に対応するので，

\sum_{j = 0}^{k} (\binom{2 k + 1}{j}) = \frac{1}{2} \sum_{j = 0}^{2 k + 1} (\binom{2 k + 1}{j}) = 2^{2 k}

である．したがって，求める値は

2^{k + 1} \cdot 2^{k} - 2^{2 k} = 2^{2 k} = 4^{k}

となる．

別解（多数派が決まる瞬間で数える）

長さ $2 k + 1$ の， $0, 1$ からなる列を考える． $0$ と $1$ の交換で対応が付くので， $1$ が多数派となる列は全体の半分，すなわち $2^{2 k}$ 個である．

一方， $k + 1$ 個目の $1$ が現れるまでに $0$ が $j$ 個現れたとすると， $0 \leq j \leq k$ である．その $1$ より前の $k + j$ 個の中で $0$ の位置を選ぶ方法は $(\binom{k + j}{j})$ 通りであり，残りの $k - j$ 個は自由に選べる．したがって同じ列を数え直すと

\sum_{j = 0}^{k} 2^{k - j} (\binom{k + j}{j}) = 2^{2 k} = 4^{k}

となる． $k = 0$ の場合もこの数え方がそのまま成り立つ．

DISCUSSION

この問題の掲示板

この掲示板は公開されています。ニックネームと本文は、ログインしていない人にも表示されます。Googleアカウントの名前は表示されません。

閲覧はどなたでもできます。ログインすると投稿できます。

まだ投稿はありません。