Let \(M\) be a nonempty set of positive integers such that \(4x\) and \(\left[ \sqrt { x } \right] \) both belong to \(M\) whenever \(x\) does.Prove that \(M\) is the set of all natural numbers.

(1) If we take the floor of square roots repeatedly we will end up with 1. Hence 1 is in M.

(2) 4 and 2 are in M.

(3) All powers of 2 are in M.

(4) Let's say k is not inside, then all numbers from \(k^{2}\) to \((k+1)^{2}-1\) are not inside, so all numbers from \(k^{4}\) to \((k+1)^{4}-1\) are not inside, ...

Hence for all natural \(n\) the numbers from \(k^{2^{n}}\) to \((k+1)^{2^{n}}-1\) are not inside.

(5) Choose \(n\) large enough such that the ratio between these two values is way greater than 2.
Contradiction!

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewest(1) If we take the floor of square roots repeatedly we will end up with 1. Hence 1 is in M.

(2) 4 and 2 are in M.

(3) All powers of 2 are in M.

(4) Let's say k is not inside, then all numbers from \(k^{2}\) to \((k+1)^{2}-1\) are not inside, so all numbers from \(k^{4}\) to \((k+1)^{4}-1\) are not inside, ...

Hence for all natural \(n\) the numbers from \(k^{2^{n}}\) to \((k+1)^{2^{n}}-1\) are not inside.

(5) Choose \(n\) large enough such that the ratio between these two values is way greater than 2. Contradiction!

Log in to reply

Joel Tan good one.I have similar thing.For your 5th step I have something..

\(f\left( x \right) =\log _{ 2 }{ x } \) defined for \({ R }_{ + }\rightarrow R\) is increasing and hence we have

\(\log _{ 2 }{ (n+1) } -\log _{ 2 }{ n } >0\)

Since \(g\left( x \right) ={ 2 }^{ -x }\) is decreasing,for a sufficiently large positive integer \(h\) we will have

\({ 2 }^{ -h }<\log _{ 2 }{ (n+1) } -\log _{ 2 }{ n } \quad \)

Which implies \({ (n+1) }^{ { 2 }^{ h } }>{ 2n }^{ { 2 }^{ h } }\)

Therefore interval \([{ n }^{ { 2 }^{ h } },{ 2n }^{ { 2 }^{ h } }]\quad \) is totally contained in \([{ n }^{ { 2 }^{ h } },{ (n+1) }^{ { 2 }^{ h } })\quad \).

But \([{ n }^{ { 2 }^{ h } },{ 2n }^{ { 2 }^{ h } }]\quad \) contains a power of \(2\).A contradiction.

Log in to reply

Nihar Mahajan,Sharky Kesa,Satvik any one?

Log in to reply