Prove that for any positive real number $\alpha$, the number $\lfloor\alpha n^2\rfloor$ is even for infinitely many positive integers $n$.
Problem
Source: XVII Tuymaada Mathematical Olympiad (2010), Senior Level
Tags: floor function, algebra, polynomial, limit, number theory unsolved, number theory
01.08.2011 03:20
$a=1,n=1$ is odd
01.08.2011 03:25
"For infinitely many" doesn't mean "for all". E.g. if $\alpha=1$, then $[\alpha n^2]$ is even for all even $n$, and there's infinitely many of those.
13.08.2011 11:54
i tried but couldn t get anything shu can you please post he solution? i wanna see it!
13.08.2011 12:44
Shu wrote: Prove that for any positive real number $\alpha$, the number $\lfloor\alpha n^2\rfloor$ is even for infinitely many positive integers $n$. An Idea: -Asumme $\alpha$, the number $\lfloor\alpha n^2\rfloor$ is even for finite positive integers $n$. -Pick $n_1,n_2$ -We have $\left \lfloor an_1^2 \right \rfloor-\left \lfloor an_2^2 \right \rfloor=\left \lfloor 2a(n_1-n_2) \right \rfloor+\left \lfloor a(n_1-n_2)^2 \right \rfloor+b$ ($b\in \left \{ 0,1,2 \right \}$) with $n_2,n_1$ enough to large we have $\left \lfloor a(n_1-n_2)^2 \right \rfloor$ is odd -Use Krocnecker theorem we obtain contradiction. Who can to continue? Sorry ,I don't know English
15.08.2011 06:07
I had a different idea: Lets separate the problem in 2 cases: $\alpha$ is rational: If $\alpha=\frac{p}{q}$, with p and q integers, just consider $n=2qk$ where $k$ is an integer. Then $ \lfloor\alpha n^2\rfloor=\lfloor4pqk^2\rfloor=4pqk^2$ that is even. $\alpha$ is irrational: Consider the binary expression $\alpha=...a_0,a_1a_2a_3a_4...$ Suppose that there are only finitely many n such that $\lfloor\alpha n^2\rfloor$ is even. Then for m large enough $m$, $\lfloor\alpha (2^m)^2\rfloor=\lfloor...a_{2m},a_{2m+1}a_{2m+2}a_{2m+3}...\rfloor$ is always odd, so $a_{2m}=1$, and we have $\alpha=...1a_{2m+1}1a_{2m+3}1...$ for large $m$. Now consider $\beta=\lfloor\alpha (3\cdot2^m)^2\rfloor=\lfloor\alpha\cdot 9\cdot2^{2m}\rfloor=\lfloor\alpha \cdot2^{2m}+\alpha\cdot2^{2m+3}\rfloor$, that must be odd for large enough $m$. But $\beta=\lfloor\alpha \cdot2^{2m}+\alpha\cdot2^{2m+3}\rfloor=\lfloor...1,a_{2m+1}1a_{2m+3}1...+...a_{2m+3},1a_{2m+5}1a_{2m+7}...\rfloor\equiv$ $\lfloor1+a_{2m+3}+0,a_{2m+1}1a_{2m+3}1...+0,1a_{2m+5}1a_{2m+7}...\rfloor(mod 2)$ But $0,a_{2m+1}1a_{2m+3}1...+0,1a_{2m+5}1a_{2m+7}...>0,010101...+0,101010...=1$, and $0,a_{2m+1}1a_{2m+3}1...+0,1a_{2m+5}1a_{2m+7}...<0,111111...+0,111111...=2$,then $\lfloor1+a_{2m+3}+0,a_{2m+1}1a_{2m+3}1...+0,1a_{2m+5}1a_{2m+7}...\rfloor=1+a_{2m+3}+1$. Since $\beta$ is odd, $2+a_{2m+3}$, must be odd, so $a_{2m+1}=1$ for any large $m$. It follows that $\alpha$ is rational, a contradiction. (Im not sure about the solution, please say if there are any mistakes)
16.04.2012 21:44
Shu wrote: Prove that for any positive real number $\alpha$, the number $\lfloor\alpha n^2\rfloor$ is even for infinitely many positive integers $n$. Let's First define $\overline{a_na_{n-1}...a_1a_0,b_1b_2...b_m}_{(2)}=a_n\times 2^n+a_{n-1}\times 2^{n-1}+...+a_1\times 2^1+a_0\times 2^0+b_1\times 2^{-1}+b_2\times 2^{-2}+...+b_m\times {2^{-m}}$ Let $P(n)=\left\lfloor n^2\alpha \right \rfloor$. First Case: $\alpha$ is a rational number such that $p,q\in \mathbb{Z}:\alpha =\frac{p}{q}$. Then it's easy to see that $\forall n\in \mathbb{N}:P(2^nq)\in Even\:Numbers$. So we're done here. Second Case: $\alpha$ is irrational. then we can write $\alpha$ in binary digits form (an infinite set from right!) like this: $a_i,b_i\in \left \{ 0,1 \right \}:\alpha =\overline{a_ma_{m-1}...a_1a_0,b_1b_2...}_{(2)}$ If we have infinity $b_{2k+1}=0$ then we may choose $n=2^{k+1}$ and then it's easy to get that $P(n)$ would be an even number! So from one $b_i$ all the $b_{odd}=1$. Now let $n>\frac{i}{2}$ and it's obvious that $P(2^n),P(3.2^n)$ are both odd.Let $2^{2n}\alpha \equiv \overline{1,k_11k_21k_31...}_{(2)}\:(mod\:2)$. So: $P(3.2^n )\equiv \left \lfloor 2^{2n}\alpha +2^{2n+3}\alpha \right \rfloor\equiv \left \lfloor \overline{1,k_11k_21k_31...}_{(2)}+\overline{k_2,1k_31...}_{(2)} \right \rfloor\equiv \left \lfloor \overline{(k_2+1),(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor\equiv 1\:(mod\:2)$ Now we have two Sub-Cases: Sub-Case 1: $\left \lfloor \overline{(k_2+1)/(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor=1 \Rightarrow k_1=k_2=k_3=k_4=...=0$ Because if $\exists i:k_i=1$ then the first binary digit(from left) would be at least $2$! so all of them are zero! So $\alpha=\overline{a_ma_{m-1}...a_2a_1a_0,b_0b_1...b_t101010101...}_{(2)}$ and it's obvious that it's a rational number! Contradiction! Sub-Case 2: $\left \lfloor \overline{(k_2+1)/(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor=3\Rightarrow k_2=1$ So $\forall i\in \mathbb{N}$ the similar way for $P(3.2^{n+i})$ we can prove that $k_{i+2}=1$. So $\alpha =\overline{a_ma_{m-1}...a_2a_1a_0,b_0b_1...b_{t'}111111...}_{(2)}$ and again it's obvious that it's a rational number! Contradiction! $Q.E.D.$
05.05.2012 19:25
Shu wrote: Prove that for any positive real number $\alpha$, the number $\lfloor\alpha n^2\rfloor$ is even for infinitely many positive integers $n$. Solution: [url=http://www.artofproblemsolving.com/Forum/memberlist.php?mode=viewprofile&u=107075]hadikh[/url] wrote: First we prove that for at least one $n\in \mathbb{N}$ $\left \lfloor n^2\alpha \right \rfloor$ is even! Assume the contray! Suppose that all the numbers $\left \{ \left \lfloor n^2\alpha \right \rfloor:n\in \mathbb{N} \right \}$ are odd! Now let $f:\mathbb{N}\rightarrow \mathbb{N}\cup \left \{ 0 \right \}$ be a function such that $f(n)<n^2$ and $\frac{f(n)}{n^2}\leq \left \{ \alpha \right \}< \frac{f(n)+1}{n^2}$.So: $f(n)\leq n^2\left \{ \alpha \right \}< f(n)+1\implies f(n)=\left \lfloor n^2\left \{ \alpha \right \} \right \rfloor$ $\Rightarrow \left \{ n^2\left \{ \alpha \right \} \right \}=n^2\left \{ \alpha \right \}-\left \lfloor n^2\left \{ \alpha \right \} \right \rfloor=n^2\left \{ \alpha \right \}-f(n)\Rightarrow \left \{ n^2\left \{ \alpha \right \} \right \}=n^2\left \{ \alpha \right \}-f(n)$ $\textbf{(1)}$ It's so easy to prove that $\{n^2\alpha\}=\{n^2\{\alpha\}\}$ so by $\textbf{(1)}$ we have: $\left \{ n^2\alpha \right \}=n^2\left \{ \alpha \right \}-f(n)\implies \left \lfloor n^2\alpha \right \rfloor=n^2\alpha -\left \{ n^2\alpha \right \}=n^2\alpha-n^2\left \{ \alpha \right \}+f(n)=n^2\left \lfloor \alpha \right \rfloor+f(n)$ $\implies 1\equiv \left \lfloor n^2\alpha \right \rfloor=n^2\left \lfloor \alpha \right \rfloor+f(n)\equiv n^2+f(n)\equiv n+f(n)\implies f(n)\not\equiv n\:(mod\:2)$ $\textbf{(2)}$ Now let $A_n:=\bigcup_{a\in B_n}\left [ \frac{a}{n^2},\frac{a+1}{n^2} \right )$ and $B_n:=\{a\in\mathbb{Z}_{\geq0}:a<n^2\; ,a\neq n\textrm{ (mod 2)}\}$. In fact $B_n$ is the Range of $f$ and $A_n$ is the range of $\left \{ \alpha \right \}$. So $\{\alpha\}\in A_n (\forall n\in\mathbb{N})$ and it implies that $%Error. "inline" is a bad command. \{\alpha\}\in \bigcap_{n=1}^{\infty }A_n$ so $%Error. "inline" is a bad command. \bigcap_{n=1}^{\infty }A_n\neq \varnothing$. With calculations you'll get that $%Error. "inline" is a bad command. \bigcap_{n=2}^{6}A_n=\varnothing$ so $%Error. "inline" is a bad command. \{\alpha\}\in\bigcap_{n=1}^{\infty }A_n\subseteq \bigcap_{n=2}^{6}A_n=\varnothing$. Contradiction! So there's at least one natural $n$ such that $2|\lfloor n^2\alpha \rfloor$. Now suppose that there are just finite natural numbers such that $2|\lfloor n^2\alpha \rfloor$.Suppose that they are $n_1<n_2<...<n_k$. If $\alpha'=m^2\alpha$ such that $n_k<m\in\mathbb{N}$, then it would be true for $\alpha'$ too! it means that there exists a natural $n$ such that $\lfloor (mn)^2\alpha\rfloor=\lfloor n^2\alpha'\rfloor=0\textrm{ (mod 2)}$. but $mn\geq m> n_k$ so we have found a greater coefficient!Again Contradiction! Hence The Result!
06.05.2012 18:17
Here's something to ponder: If $P$ is a polynomial with at least one irrational nonconstant coefficient, then it is well known that $\{P(n)\}$ is equidistributed mod 2. In particular, \[\lim_{N\to\infty} \frac{1}{N}|\{n\le N : P(n)\in [0,1)\,\mathrm{mod}\,2\}| = \frac{1}{2}\] $P(n)\in [0,1)\,\mathrm{mod}\,2$ is equivalent to $2|\lfloor P(n)\rfloor$. If $\alpha$ is irrational, then let $P(n) = \alpha n^2$. (Of course, if $\alpha$ is rational, the problem is trivial.) This problem can be generalized considerably: Vinogradov proved that if $\alpha$ is irrational, $\{\lfloor \alpha p \rfloor: p\in\mathbb{P}\}$ is equidistributed mod 2. So if $\alpha$ is irrational, there are infinitely many primes $p$ such that $\lfloor \alpha p\rfloor$ is even. (This could be false if $\alpha$ is rational: if $\alpha = 3$, then the only such prime is $p=2$).
09.06.2014 22:01
a-irrational then if such n is finite we have [(n^2)a]-odd for all n >M so if a=b+c where b is =[a] and c={a}then take even n >M then [(n^2)c]-odd the [((n+1)^2)c]-even then odd ..even but how can we come for contradiction?
24.01.2023 14:08