Let $X$ be a non-empty set of positive integers which satisfies the following: if $x \in X$, then $4x \in X$, if $x \in X$, then $\lfloor \sqrt{x}\rfloor \in X$. Prove that $X=\mathbb{N}$.
Problem
Source:
Tags: floor function, induction, logarithms
06.10.2007 18:04
Let $ m\in X$ the smallest element of $ X$. Then $ m\le[\sqrt m]$, from where $ m=1$. Then $ 4^k\in X$, $ \forall k\in\mathbb{N}_0$, from where $ 2^k=[\sqrt{4^k}]\in X$, $ \forall k\in\mathbb{N}_0$. All powers of $ 2$ are in $ X$. Now suppose some $ t\notin X$. Then the equation ($ n$ is the unknown) $ t=[\sqrt n]$ has no solution $ n\in X$. This means that $ \forall m$, $ t^2\le m<(t+1)^2$, $ m\notin X$. We prove by the induction on $ k\ge1$ that if $ t^{2^k}\le m<(t+1)^{2^k}$, then $ m\notin X$. Base case $ k=1$ is proved. Suppose for some $ k$ we have proved this claim. Now take $ m$ such that $ t^{2^{k+1}}\le m<(t+1)^{2^{k+1}}$. Suppose $ m\in X$. Then $ [\sqrt m]\in X$. But $ t^{2^k}\le[\sqrt m]\le\sqrt{m}<(t+1)^{2^k}$, contradicting the induction hypothesis. Now suppose some $ X\neq \mathbb{N}$. Assume some $ l\notin X$. Then $ l\ge3$. Let $ x=\log_2l$, $ y=\log_2(l+1)$. As we have proved, for any $ k\ge2$, no positive integer in $ [l^{2^k},(l+1)^{2^k})$ is in $ X$, or no positive integer in $ [2^{2^kx},2^{2^ky})$ is in $ X$. Because we have proved that all powers of $ 2$ are in $ X$, this means that no positive integer is in the interval $ [2^kx,2^ky)$ for any $ k$, implying that $ 2^k(y-x)<1$. However $ y-x>0$ is a fixed positive real number, while $ k$ is as big as we want, so $ 2^k(y-x)$ is not bounded. Contradiction. Thus $ X=\mathbb{N}$.
24.05.2009 10:38
Very nice solution And I had another approach. Step 1$ [\sqrt {\sqrt {[x]}}]=[\sqrt {\sqrt {x}}]$ Step 2:$ 1\in X$ Step 3:$ [2^{\frac{n}{2^{m-1}}}]\in X$for all positive integers $ m,n$ Step 4:For a certain $ n \in N,n\ge 2$Choose $ m$ sufficiently large so that $ 2^{\frac{1}{2^{m-1}}}$$ \le \frac{n}{n-1}$ Then $ n\in X$ QED