Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 238 A問題 Exponential or Quadratic

AtCoder ABC ABC238 A問題 100 pts

問題

提出解答

問題の概要

$2^n \gt n^2$ か?

制約

$1 \leq n \leq 10^9$

解法

結論から言うと, $n=2,3,4$ のときは否定的で, $n=1$ または $n \geq 5$ のときは肯定的である. よって, $n$ を受け取って, 肯定的か否定的かを判定すれば良い.

ここからはこのことを数学的帰納法を用いて証明する.

$n=1,2,3,4,5$ のときは直接計算で示される.
$n ~(n \geq 5)$ のときに正しいとする. このとき, 数学的帰納法の仮定から,

$2^{n+1}-(n+1)^2=2 \cdots 2^n -(n+1)^2 \gt 2 n^2-(n+1)^2=n^2-2n-1=(n-1)^2-2$

であり, $n \geq 5$ であるから, $2^{n+1} \gt (n+1)^2$ である.

よって, 判定法が正しいことが示された.