### 34th Putnam 1973

Problem A3

n is a positive integer. Prove that [√(4n + 1) ] = [ min (k + n/k) ], where the minimum is taken over all positive integers k.

Solution

We evaluate each side. It is probably easiest to tackle [√(4n + 1) ] first. Let f(n) = [√(4n + 1) ]. If n ≤ m2 - 1, then 4n + 1 ≤ 4m2 - 3 < (2m)2, so f(n) < 2m. If n ≥ m2, then 4n + 1 > 4m2, so f(n) ≥ 2m. If n < m(m+1), then 4n + 1 < 4m2 + 4m + 1 = (2m+1)2, so f(n) < 2m+1. If n ≥ m(m+1), then 4n+1 ≥ (2m+1)2, so f(n) ≥ 2m+1. Hence for n = m2, m2 + 1, m2 + 2, ... , m2 + m - 1, we have f(n) = 2m. For n = m2 + m, m2 + m + 1, m2 + m + 2, ... , m2 + 2m we have f(n) = 2m+1.

Let g(n) be the minimum value of [k + n/k], where k is a positive integer. Consider h(x) = x + n/x, with x real and positive. h'(x) <0, =0, >0 according as x <√n, =√n, >√n. So for positve real x, the smallest value of x + n/x occurs at x = √n and the smallest value with x restricted to be an integer must occur at [√n] or [√n] + 1.

For n = m2, m2 + 1, m2 + 2, ... , m2 + m - 1, we have [√n] = m. Also 0 < (m-1)/m < 1, so [m + n/m] = 2m. Now n > m2 - 1, so n/(m+1) > m - 1 and hence [(m+1) + n/(m+1)] ≥ [m+1 + m-1] = 2m. So for these values of n we have g(n) = 2m = f(n).

Now consider n = m2 + m, m2 + m + 1, m2 + m + 2, ... , m2 + 2m. For these values of n also we have [√n] = m. For all except the last value of n, we have [m + n/m] = 2m+1. For the last we have [m + n/m] = 2m+2. But for all of them we have [(m+1) + n/(m+1)] = 2m+1. Hence for these values of n also g(n) = 2m+1 = f(n).