# How do I solve this Olympiad question with floor functions?

Emmy is playing with a calculator. She enters an integer, and takes its square root. Then she repeats the process with the integer part of the answer. After the third repetition, the integer part equals 1 for the first time. What is the difference between the largest and the smallest number Emmy could have started with?

$$\text{(A)} \; 229 \qquad \text{(B)} \; 231 \qquad \text{(C)} \; 239 \qquad \text{(D)} \; 241 \qquad \text{(E)} \; 254$$

This was Problem 19 from the first round of the Norwegian Mathematical Olympiad, 2014–15.

I think the floor function applies well here.

The integer part obviously is the floor part of it.

Let $x_1$ be the initial.

$x_2 = \left \lfloor{{\sqrt{x_1}}}\right \rfloor$

$x_3 = \left \lfloor{{\sqrt{x_2}}}\right \rfloor$

$x_4 = \left \lfloor{{\sqrt{x_3}}}\right \rfloor = 1$ <-- Last one.

So we need to find $b \le x_1 \le c$ such that $b$ is the smallest number to begin with and $c$ is the largest number to begin with.

$\sqrt{b} \le \sqrt{x_1} \le \sqrt{c}$

Clearly we must have $x_3<4$, $x_2<16$, and $x_1<256$, so the largest possible value of $x_1$ is $255$. Since $x_3>1$, we know that $x_3\ge 2$ and hence that $x_2\ge 4$. This implies that $x_1\ge 16$. Thus, the range is from $16$ through $255$, the difference being $239$.

• @BrianScott, Thanks. Clear up, why must we have those conditions? Why $x_1 < 256$? – Robart Jan 24 '15 at 18:05
• We know that $x_4=1$, so $1\le\sqrt{x_3}<2$, and therefore $x^3<2^2=4$. Now repeat the reasoning back up the line: $x_3<4$, so $\sqrt{x_2}<4$, and $x_2<16$. And so on. – Brian M. Scott Jan 24 '15 at 18:06
• @Robart: Sorry: I forgot to ping you with my answer. See the comment immediately above this one. – Brian M. Scott Jan 24 '15 at 18:13
• why cant she start with $x_1 = 1$ so the difference is $255 - 1 = 254$? – Robart Jan 24 '15 at 18:43
• @Robart: Because we’re told that $x_4$ is the first of these integers to be equal to $1$. – Brian M. Scott Jan 24 '15 at 18:45

We can work backwards more easily than we can work forwards. Firstly, what does a number $x$ need to satisfy to have $\lfloor x \rfloor = 1$? Easy. We need: $$1\leq x < 2.$$ Well, suppose that $\sqrt{y}=x$ or, equivalently, $y=x^2$. Well, obviously we just square the above equation (as all of its terms are positive): $$1\leq x^2 < 2^2.$$ Suppose $\sqrt{z}=y$ or $z=y^2=x^4$. Square the above again! $$1\leq x^4 < 2^4.$$ And finally let $\sqrt{w}=z$ or $w=z^2=y^4=x^8$. Square the above $$1\leq x^8 < 2^8.$$

So, if she chose $z$ to be any integer in $[1,2^8)$, she will get $1$ as the final result. However, if $z$ were in the interval $[1,2^4)$, she would have gotten $1$ as the second result as well. So, we restrict ourselves to the integers in $[2^4,2^8)$, as these will satisfy the desired condition.

• And how do you pick the smallesT? Its supposed to be $16$? – Robart Jan 24 '15 at 18:33
• Yes, the condition that the third time is the first time that the number is $<2$ means that $x^2\geq 2$. – Thomas Andrews Jan 24 '15 at 18:35
• Why does it have to be $x^2 \ge 2$? then $x ge \sqrt{2}$ – Robart Jan 24 '15 at 18:41
• It should be 254 I believe. The smallest is $1$ since $\sqrt{1} = 1$ for $n$ square roots. – Robart Jan 24 '15 at 18:43
• @Robart The question says that the third time is the first for which the result is $1$ - the greatest possible number is $255$, as higher numbers don't reach $1$ fast enough, and the least is $16$, as lower numbers reach $1$ too fast. – Milo Brandt Jan 24 '15 at 18:46