2
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @BrianScott, Thanks. Clear up, why must we have those conditions? Why $x_1 < 256$? $\endgroup$ – Robart Jan 24 '15 at 18:05
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Jan 24 '15 at 18:06
  • $\begingroup$ @Robart: Sorry: I forgot to ping you with my answer. See the comment immediately above this one. $\endgroup$ – Brian M. Scott Jan 24 '15 at 18:13
  • $\begingroup$ why cant she start with $x_1 = 1$ so the difference is $255 - 1 = 254$? $\endgroup$ – Robart Jan 24 '15 at 18:43
  • $\begingroup$ @Robart: Because we’re told that $x_4$ is the first of these integers to be equal to $1$. $\endgroup$ – Brian M. Scott Jan 24 '15 at 18:45
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And how do you pick the smallesT? Its supposed to be $16$? $\endgroup$ – Robart Jan 24 '15 at 18:33
  • $\begingroup$ Yes, the condition that the third time is the first time that the number is $<2$ means that $x^2\geq 2$. $\endgroup$ – Thomas Andrews Jan 24 '15 at 18:35
  • $\begingroup$ Why does it have to be $x^2 \ge 2$? then $x ge \sqrt{2}$ $\endgroup$ – Robart Jan 24 '15 at 18:41
  • $\begingroup$ It should be 254 I believe. The smallest is $1$ since $\sqrt{1} = 1$ for $n$ square roots. $\endgroup$ – Robart Jan 24 '15 at 18:43
  • $\begingroup$ @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. $\endgroup$ – Milo Brandt Jan 24 '15 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.