A - Exponential or Quadratic Editorial by en_translator
To come to the point, the answer is Yes if \(2 \leq n \leq 4\) and No otherwise.
It can be easily asserted that \(2^n \gt n^2\) if \(n=1\) and \(2^n \leq n^2\) if \(2 \leq n \leq 4\).
What about \(5 \leq n\)? It can be proved by induction that \(2^n \gt n^2\).
Actual proof
First, it is obvious that $2^n \gt n^2$ if $n=5$. $\cdots$ (1)
We will now prove that, (☆) for any integer $k$ greater than or equal to $5$, if $2^n \gt n^2$ for $n=k$ then it also holds that $2^n \gt n^2$ for $n=k+1$.
First, by assumption $2^{k+1}=2 \times 2^k \gt 2k^2$, and $2k^2$ can be transformed as follows.
$2k^2 = (k^2+2k+1)+(k^2-2k-1) = (k+1)^2+(k-1)^2-2$
Since $4 \leq k-1$ for $5 \leq k$, so $(k-1)^2-2$ is always greater than or equal to $14$, so it is positive.
Therefore, for $5 \leq k$, if $2^n \gt n^2$ for $n=k$ then we have $2^{k+1} = 2 \times 2^k \gt 2k^2 \gt (k+1)^2$, so ☆ has been proved. $\cdots$ (2)
(1) and (2) shows shat $2^n \gt n^2$ if $5 \leq n$.
Sample code (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;
}
Alternatively, we can solve this problem based on assumption that \(2^n \gt n^2\) for a certainly large \(n\).
Sample code (Python)
n = int(input())
n = min(n,10)
ans = 'No'
if pow(2,n) > n*n:
ans = 'Yes'
print(ans)
posted:
last update: