Let $X$ be a non empty subset of $\mathbb{N} = \{1,2,\ldots \}$. Suppose that for all $x \in X$, $4x \in X$ and $\lfloor \sqrt{x} \rfloor \in X$. Prove that $X=\mathbb{N}$.
Problem
Source: French TST 2005 pb 4.
Tags: floor function, ceiling function, induction, inequalities, logarithms, number theory unsolved, number theory
Igor
27.05.2005 15:48
Main idea: (I'll hide it if you don't want to see it) :
$1 \in X$ and $\forall k \in \mathbb{N}^*$, $4^k \in X$.
And for $x,k,n \in \mathbb{N}^*$, $\quad \frac{\textrm{ln}(1+\frac{1}{x})}{\textrm{ln}(2)} \geq \frac{1}{2^{n-1}}\Longrightarrow
x^{2^n}\leq 4^k < {(x+1)}^{2^n}$.
Take $n$ sufficiently large and after applying step 2 on $4^k$ $n$ times we get $x \in X$.
rookworm
29.05.2005 09:32
Igor wrote: Define $[u]$ as the integer part of any real $u$. Let $X$ be a non empty subset of $\mathbb{N}^*$. Suppose that for all $x \in X$, $4x \in X$ and $[\sqrt{x}] \in X $. Prove that $X=\mathbb{N}^*$ Link to the test what is $X=\mathbb{N}^*$ ? Surely it is not the group of unit natural numbers i.e. the trivial group $\{1\}$....
Igor
29.05.2005 10:51
$\mathbb{N}^*$ is the set $\{1,2,3,4,\ldots\}$.
Vahe Musoyan
24.06.2005 14:28
Why do you put * next to $\mathbb{N}$:?:
cyberjoe
25.06.2005 00:03
Obviously for any integer k we have 4^k \in X. Thus \lfloor \sqrt{4^k} \rfloor = 2 k \in X, so for any integer m, we also have 4 m \in X. Thus \lfloor \sqrt{4 m} \rfloor = \lfloor 2 \sqrt{m} \rfloor \in X, for any integer m. Let's take m = \lceil \frac{a^2}{4} \rceil for a given integer a \geqslant 2 then \lfloor 2 \sqrt{m} \rfloor = a, the conclusion follows...
Vahe Musoyan
25.06.2005 08:21
Maybe I don't understand something, but $\lfloor \sqrt{4^k} \rfloor = 2^k$ not $2 k$. So you can say that only powers of 2 are in $X$, and nothing more. After that Igor's solution is the only way I think.
cyberjoe
25.06.2005 13:11
Yes, of course... sorry (I really don't know why I tought that sqrt(4^k)=2*k )
indybar
31.07.2005 09:15
Are there other solutions?
Maharjun
19.03.2010 20:59
My solution is mainly using first principle of mathematical induction Part 1:
this is basically a rigorous representation of common sense
let $ f\left( x \right) = \left[ {{x^{1/2}}} \right]$
$ \& f\left( x \right) \le {x^{1/2}} \\
\& f \circ f\left( x \right) \le \left( {f{{\left( x \right)}^{1/2}}} \right) \le {\left( {{x^{1/2}}} \right)^{1/2}} \le {x^{1/{2^2}}} \\
\& \implies {f^n}\left( x \right) \le {x^{1/{2^n}}}$
Also we know that
$ {\text{If }}x \in X \implies {f^n}\left( x \right) \in X{\text{ }}\forall {\text{ }}n \in {\Bbb N}$
for any particular $ x \in X$
let $ g(n) = f^n(x)$
$ \& 1 \le g\left( n \right) \le {x^{1/{2^n}}} \\
\& {\text{as }}n \to \infty ,{x^{1/{2^n}}} \to 1 \\
\& \implies {\text{ For some }}n \in {\Bbb N}{\text{ we have }}{{\text{x}}^{1/{2^n}}} < 2 \implies g\left( n \right) = {f^n}\left( x \right) = 1$
$ %Error. "since" is a bad command.
g(n) \in X \ \forall \ \n \in \Bbb N \implies \boxed{1 \in X}$
Part 2.
If $ x \in X \implies 4^nx \in X \ \forall n\in \Bbb N$
Now our task is to show that there exists a number of form $ 4^nx$ for every $ x\in X$ such that after repeatedly rooting and finding greatest integer, we get $ x + 1$.
thus we must prove that there exists a number $ 4^nx$ such that $ (x + 1)^{2^n} \le 4^kx < (x + 2)^{2^n}$ where $ n ,k \in N$
Why so?$ %Error. "eqalign" is a bad command.
{ \& {(x + 1)^{{2^n}}} \le {4^k}x < {(x + 2)^{{2^n}}} \\
\& \implies {(x + 1)^{{2^{n - 1}}}} \le \sqrt {{4^k}x} < {(x + 2)^{{2^{n - 1}}}} \\
}$
${ \& \implies {(x + 1)^{{2^{n - 1}}}} \le \left[ {\sqrt {{4^k}x} } \right] < {(x + 2)^{{2^{n - 1}}}} - - - - - \left[ {\because {{(x + 1)}^{{2^{n - 1}}}}{\text{ and }}{{(x + 2)}^{{2^{n - 1}}}} \in {\Bbb N}} \right] \\
\& \dots \\
\& \dots \\
\& \dots \\
\& \implies (x + 1) \le \left[ {\sqrt {\left[ {\sqrt {\dots \left[ {\sqrt {{4^k}x} } \right]} } \right]} } \right] < x + 2 \\
\& \implies \left[ {\sqrt {\left[ {\sqrt {\dots \left[ {\sqrt {{4^k}x} } \right]} } \right]} } \right] = x + 1 \in X }$
the inequality can be rewritten as-
\[ \& {4^{{2^n}{{\log }_4}\left( {x + 1} \right)}} \le {4^{k + {{\log }_4}\left( x \right)}} < {4^{{2^n}{{\log }_4}\left( {x + 2} \right)}} \\
\& \Leftrightarrow {4^{{2^n}{{\log }_4}\left( {x + 1} \right) - {{\log }_4}\left( x \right)}} \le {4^k} < {4^{{2^n}{{\log }_4}\left( {x + 2} \right) - {{\log }_4}\left( x \right)}}\]
consider the case of $ k = \left[ {{2^n}{{\log }_4}\left( {x + 1} \right) - {{\log }_4}\left( x \right)} \right] + 1 = \left[ {{2^n}{{\log }_4}\left( {x + 1} \right) - {{\log }_4}\left( x \right) + 1} \right]$
we know that $ k < {2^n}{{\log }_4}\left( {x + 2} \right) - {{\log }_4}\left( x \right)$
so,
\[ \left[ {{2^n}{{\log }_4}\left( {x + 1} \right) - {{\log }_4}\left( x \right) + 1} \right] < {2^n}{\log _4}\left( {x + 2} \right) - {\log _4}\left( x \right) \\
\Leftarrow {2^n}{\log _4}\left( {x + 1} \right) - {\log _4}\left( x \right) + 1 < {2^n}{\log _4}\left( {x + 2} \right) - {\log _4}\left( x \right)\]
\[ \& \Leftrightarrow 4{\left( {x + 1} \right)^{{2^n}}} < {\left( {x + 2} \right)^{{2^n}}} \\
\& \Leftrightarrow 4 < {\left( {1 + \frac {1} {{x + 1}}} \right)^{{2^n}}}\]
which is true if we take arbitrarily high values of $ n$
hence, for every value of x, we have such a number $ 4^kx$
hence $ \because x \in X \implies 4^kx \in X \implies (x + 1) \in X$
hence $ x\in X \forall x \in \Bbb N$