[Soln] 2013 APMO Problem 2

2013 APMO 2. Determine all positive integers n for which \displaystyle \frac{n^2+1}{[\sqrt{n}]^2 + 2} is an integer. Here [r] denotes the greatest integer less than or equal to r.

I calculated the fraction for n = 1, 2, \dots 16 and found that none of them satisfied the given condition:

APMO_2013_2With none of the first 16 values of n satisfying the given condition, I began to suspect that the fraction can never be an integer.

With that in mind, I began to manipulate the given fraction into something that is easier to analyse. When dealing with floor functions, it is often useful to introduce variables for the integer and fractional parts. In this problem, it means writing [\sqrt{n}] as another variable k, then expressing n in terms of k.

Let k := [\sqrt{n}]. Then we can write n := k^2 + \alpha, where \alpha = 0, 1, \dots, 2k. Now, I can think of the problem in a slightly different manner:

I want to find all positive integers k such that the fraction \displaystyle\frac{(k^2 + \alpha)^2 + 1}{k^2 + 2} is an integer for some \alpha = 0, 1, \dots, 2k.

Notice that in the fraction above, the numerator has k to the 4th power while the denominator only has k to the 2nd power. A common trick is to perform long division so that the numerator has lower degree than the denominator. (When the numerator has lower degree, for large enough values of k the numerator will be smaller than the denominator, and hence cannot be an integer. This helps to restrict the search space.)

Performing long division:

\begin{aligned} \frac{(k^2 + \alpha)^2 + 1}{k^2 + 2} &= k^2 + 2\alpha - 2 + \frac{\alpha^2 - 4\alpha + 5}{k^2 + 1} \\  &= k^2 + 2\alpha - 2 + \frac{(\alpha - 2)^2 + 1}{k^2 + 1}. \end{aligned}

Hence, the original fraction is an integer if and only if \frac{(\alpha - 2)^2 + 1}{k^2 + 1} is an integer.

Remember that \alpha can only take on specific values! In fact, when \alpha takes on its maximum value of 2k, the fraction above becomes

\begin{aligned} \frac{(2k-2)^2 + 1}{k^2 + 1} &= \frac{4k^2 - 8k + 5}{k^2 + 2} \\  &< \frac{4k^2 + 8}{k^2 + 2} = 4, \end{aligned}

hence the fraction can only take on the values of 1, 2 and 3. We can evaluate each of these cases separately.

Case 1: \frac{(\alpha - 2)^2 + 1}{k^2 + 2} = 1
Simplifying, we get

(\alpha - 2)^2 - k^2 = 1,

which does not have any solution in positive k since no 2 consecutive squares are so close together.

Case 2: \frac{(\alpha - 2)^2 + 1}{k^2 + 2} = 2
Simplifying, we get

(\alpha - 2)^2 = 2k^2 + 3.

However, considering this equation in mod 8, we can see that there is no solution. In mod 8, all squares must be congruent to 0, 1, or 4, i.e. \text{LHS} \equiv 0,1,4 (\mod 8). However, by the same token this means that \text{RHS} \equiv 2 \times (0,1,4) + 3 \equiv 3, 5 (\mod 8).

Case 3: \frac{(\alpha - 2)^2 + 1}{k^2 + 2} = 3
Simplifying, we get

(\alpha - 2)^2 = 3k^2 + 5.

However, considering this equation in mod 3, we can see that there is no solution.

In conclusion, there is no positive integer k such that the fraction \displaystyle\frac{(k^2 + \alpha)^2 + 1}{k^2 + 2} is an integer for some \alpha = 0, 1, \dots, 2k. Hence, there is no positive integer n such that \displaystyle \frac{n^2+1}{[\sqrt{n}]^2 + 2} is an integer. QED.

(Note: For problems where you are supposed to find solutions to equations, it is often a good idea to consider the equation modulo n for various n to constrain the values which the variables can take. For example,

\begin{aligned} &x^2 \text{ must be congruent to } 0 \text{ or } 1 &&\text{mod 3}, \\  &x^2\text{ must be congruent to } 0 \text{ or } 1 &&\text{mod 4} \\  &x^2\text{ must be congruent to } 0, -1 \text{ or } 1 &&\text{mod 5} \\  &\dots && \end{aligned}

It’s good to remember which modulos are good for constraining the values of which powers.)

 

Advertisements
This entry was posted in Grade 12, Intl/Regional and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s