A - Exponential or Quadratic Editorial by penguinman
結論から言うと、\(2 \leq n \leq 4\) のとき答えは No、そうでないとき答えは Yes となります。
\(n=1\) のとき \(2^n \gt n^2\) であること、および \(2 \leq n \leq 4\) において \(2^n \leq n^2\) であることは実際に計算すれば明らかです。
問題は \(5 \leq n\) のときですが、これは数学的帰納法により \(2^n \gt n^2\) であることを示すことが可能です。
具体的な証明
まず、$n=5$ のとき、明らかに $2^n \gt n^2$ である。$\cdots$ ①
その上で、任意の $5$ 以上の整数 $k$ について、$n=k$ のときに $2^n \gt n^2$ が成り立つと仮定すると $n=k+1$ のときにも $2^n \gt n^2$ が成り立つこと（☆）を示す。
まず仮定より、$2^{k+1}=2 \times 2^k \gt 2k^2$ である。そして $2k^2$ は、以下のように変形可能である。
$2k^2 = (k^2+2k+1)+(k^2-2k-1) = (k+1)^2+(k-1)^2-2$
$5 \leq k$ においては $4 \leq k-1$ が成り立つため、$(k-1)^2-2$ は常に $14$ 以上となり、正である。
故に $5 \leq k$ において、$n=k$ のときに $2^n \gt n^2$ が成り立つならば $2^{k+1} = 2 \times 2^k \gt 2k^2 \gt (k+1)^2$ という式が立てられることが分かり、よって☆は示された。$\cdots$ ②
①、② より、$5 \leq n$ であるならば $2^n \gt n^2$ であることが示せた。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
if(2 <= n && n <= 4) cout << "No" << endl;
else cout << "Yes" << endl;
}
なお、この他にも \(n\) がある程度大きい値であれば \(2^n \gt n^2\) が成り立つと予想し、それを元に問題を解くことも可能です。
実装例 (Python)
n = int(input())
n = min(n,10)
ans = 'No'
if pow(2,n) > n*n:
ans = 'Yes'
print(ans)
posted:
last update: