MHB What is the solution to this challenging number theory problem?

AI Thread Summary
The discussion focuses on a number theory problem involving a set of natural numbers, S, defined by specific membership rules. It is established that if a number x is in S, then both 4x and the floor of the square root of x are also in S, leading to the conclusion that S encompasses all natural numbers, or S = ℕ. Additionally, the conversation explores how this conclusion changes if the multiplication factor in the first rule is replaced with a variable k. Participants discuss the implications of this substitution, noting that the solution for k must allow for all natural numbers to still be included in S. The thread emphasizes the logical steps required to reach these conclusions in number theory.
Nono713
Gold Member
MHB
Messages
615
Reaction score
4
Let $S$ be a nonempty set of natural numbers, equipped with the following membership rules:
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ 4x \in S \tag{1}$$
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ \lfloor \sqrt{x} \rfloor \in S \tag{2}$$
Show that $S = \mathbb{N}$, and find all the natural numbers $k$ for which this still holds if rule $(1)$ becomes $x \in S \implies kx \in S$ (i.e. substituting $k$ instead of $4$).
 
Last edited:
Mathematics news on Phys.org
This is a fun problem! :D I have, or I think I have, a solution for the first part of the problem.

We are given that $\Bbb N \supseteq S \neq \emptyset$, thus there is a $k \in \Bbb N$ such that $k \in S$. By rule $(2)$, $\lfloor \sqrt{k} \rfloor \in S$. Repeatedly applying rule $(2)$ in this fashion $n$ times, we see that there is an integer smaller than $k^{1/2^n}$ and (not strictly) greater $1$ in $S$. However, it is clear there exists a large $n$ for which $k^{1/2^n} \leq 2$. As $S \subseteq \Bbb N$ and since the only integer in $[1, 2)$ is $1$, we conclude that $1 \in S$.

By rule $(1)$, $4 \cdot 1$ is in $S$ and by rule $(2)$, $\lfloor \sqrt{4} \rfloor = 2$ is in $S$. It is thus clear that all of the powers of $2$ are in $S$. Now note that as $\Bbb Q$ is dense in $\Bbb R$, there are (well, countably) infinitely many rationals in the interval $[\log_2(n), \log_2(n+1)]$ for some integer $n$. We can thus cutoff the two ends of this interval to produce some interval $[a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$ with rational limit points. As $a_0/b_0 < a_1/b_1$, i.e., $a_0 b_1 < a_1b_0$, we can always produce an integer $x$ inside $(a_0 b_1 \cdot 2^k, a_1 b_0 \cdot 2^k)$ for some proper choice of $k$. Thus $x/2^k \in [a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$, i.e., $n^{(2^k)} \leq 2^x \leq (n + 1)^{(2^k)}$. As $2^x \in S$, applying rule $(2)$, $k$ times, on $2^x$ results $n \in S$. As this procedure can be applied to any integer $n$, we have $S = \Bbb N$.
 
Last edited:
Well done mathbalarka for participating and correctly answering the first part of the challenge! (though I believe extending it to also solve the second part is reasonably straightforward with some minor changes). My own original solution is given below, it follows the same major steps as mathbalarka's solution but uses different tools to arrive at the result:

I will immediately prove the second part of the challenge, the first part being a special case.

We first prove the lemma that if $[a, b)$ is an interval with $ka < b$ for integers $a, b, k > 1$ then $[a, b)$ contains a power of $k$. We first note that $k^0 = 1 < a$. Now suppose $k^r < a$ for any $r \in \mathbb{N}$. Then there are three possibilities: either $k^{r + 1} < a$, $k^{r + 1} \geq b$, or $k^{r + 1} \in [a, b)$. Now $k^{r + 1} \geq b$ is impossible, since $ka < b$ and $k^r < a$ hence $k(k^r) = k^{r + 1} < b$. If $k^{r + 1} < a$, then we can repeat the argument until $k^{r + s} \in [a, b)$ for some $s > 0$, which will happen as the sequence $(k^n)_{n = 0}^\infty$ is strictly increasing.

Since $\lfloor \sqrt{1} \rfloor = 1$ and $\lfloor \sqrt{x} \rfloor < x$ for $x > 1$ since $\lfloor \sqrt{x} \rfloor^2 \leq x$, it follows that repeatedly applying rule $(2)$ starting from any integer will eventually yield 1. Since $S$ is nonempty, there exists at least one element in $S$, and thus $1 \in S$ by the above reasoning. It therefore suffices to show that $1 \in S \implies x \in S$ for all $x \in \mathbb{N}$ to prove the claim. Denote $I_n$ the interval $[x^{2^n}, (x + 1)^{2^n})$. This interval $I_n$ can be made arbitrarily large by increasing $n$, as:
$$\lim_{n \to \infty} \frac{(x + 1)^{2^n}}{x^{2^n}} = \lim_{n \to \infty} \left ( \frac{x + 1}{x} \right)^{2^n} = \infty$$
In other words, the upper bound of the interval grows faster than the lower bound, and hence $I_n$ is asymptotically unbounded in size.

Now let $k \in \mathbb{N}$ such that $x \in S \implies kx \in S$. Since $1 \in S$, repeatedly applying this rule amounts to saying that $k^r \in S$ for all $r \in \mathbb{N}$. We have seen that $I_n$ can be made arbitrarily large, thus there exists an $n$ such that $kx^{2^n} < (x + 1)^{2^n}$ for any $k$. Hence by the lemma, $k^r \in [ x^{2^n}, (x + 1)^{2^n} )$ for some $r \in \mathbb{N}$. At this point, since $k^r \in S$, it suffices to repeatedly apply rule $(2)$ on $k^r$ which is guaranteed to eventually yield $x$ by monotonicity of the square root floor function, and we conclude that $x \in S$. We have only needed $k > 1$ (for the lemma) and therefore $S = \mathbb{N}$ for all (integer) $k > 1$, including $k = 4$. $\blacksquare$​
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.

Similar threads

Back
Top