Maths Olympiad Prep

Library / /34 of 37

Algebra Difficulty 8.5 Shortlist Find the answer

Choose positive integers b1,b2,b_1, b_2, \dotsc satisfying
1=b112>b222>b332>b442>1=\frac{b_1}{1^2} > \frac{b_2}{2^2} > \frac{b_3}{3^2} > \frac{b_4}{4^2} > \dotsb
and let rr denote the largest real number satisfying bnn2r\tfrac{b_n}{n^2} \geq r for all positive integers nn. What are the possible values of rr across all possible choices of the sequence (bn)(b_n)?

[i]Carl Schildkraut and Milan Haiman[/i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let r r denote the largest real number satisfying bnn2r\frac{b_n}{n^2} \geq r for all positive integers n n , where b1,b2, b_1, b_2, \dotsc are positive integers satisfying
1=b112>b222>b332>b442> 1 = \frac{b_1}{1^2} > \frac{b_2}{2^2} > \frac{b_3}{3^2} > \frac{b_4}{4^2} > \dotsb

We aim to determine the possible values of r r .

### Claim 1: r=12 r = \frac{1}{2} works and is maximal.
To achieve r=12 r = \frac{1}{2} , consider the sequence bn=n(n+1)2 b_n = \frac{n(n+1)}{2} . Then,
bnn2=n(n+1)2n2=n+12n=12+12n, \frac{b_n}{n^2} = \frac{n(n+1)}{2n^2} = \frac{n+1}{2n} = \frac{1}{2} + \frac{1}{2n},
which satisfies the condition bnn212\frac{b_n}{n^2} \geq \frac{1}{2}.

We can inductively show that bnn(n+1)2 b_n \leq \frac{n(n+1)}{2} . The base case is given. Assuming the hypothesis holds for all integers less than n n , we have
bnn2<bn1(n1)2n2(n1)    bn<n32(n1). \frac{b_n}{n^2} < \frac{b_{n-1}}{(n-1)^2} \leq \frac{n}{2(n-1)} \implies b_n < \frac{n^3}{2(n-1)}.
It is easy to verify that the largest possible bn b_n is n(n+1)2 \frac{n(n+1)}{2} , as claimed.

### Claim 2: All r<12 r < \frac{1}{2} work.
Consider the sequence an:=kn2+n a_n := \left\lceil kn^2 \right\rceil + n for k<12 k < \frac{1}{2} . Since an a_n is O(n2) O(n^2) , there exists N N such that for all nN n \geq N ,
ann2<12. \frac{a_n}{n^2} < \frac{1}{2}.
Define the sequence bn b_n as follows:
bn:={n(n+1)2for n<N,anfor nN. b_n := \begin{cases} \frac{n(n+1)}{2} & \text{for } n < N, \\ a_n & \text{for } n \geq N. \end{cases}
By definition of N N , bnn2>bn+1(n+1)2 \frac{b_n}{n^2} > \frac{b_{n+1}}{(n+1)^2} for n<N n < N . For nN n \geq N , we want to show that
kn2+nn2>k(n+1)2+n+1(n+1)2. \frac{\left\lceil kn^2 \right\rceil + n}{n^2} > \frac{\left\lceil k(n+1)^2 \right\rceil + n + 1}{(n+1)^2}.
Since kn2kn2 \left\lceil kn^2 \right\rceil \geq kn^2 ,
kn2+nn2k+1n, \frac{\left\lceil kn^2 \right\rceil + n}{n^2} \geq k + \frac{1}{n},
and since k(n+1)2<k(n+1)2+1 \left\lceil k(n+1)^2 \right\rceil < k(n+1)^2 + 1 ,
k(n+1)2+n+1(n+1)2<k+n+2(n+1)2. \frac{\left\lceil k(n+1)^2 \right\rceil + n + 1}{(n+1)^2} < k + \frac{n+2}{(n+1)^2}.
It suffices to verify that
1nn+2(n+1)2    (n+1)2n(n+2), \frac{1}{n} \geq \frac{n+2}{(n+1)^2} \iff (n+1)^2 \geq n(n+2),
which is true.

Combining these two claims, we conclude that the possible values of r r are:
0r12. 0 \leq r \leq \frac{1}{2}.

The answer is: \boxed{0 \leq r \leq \frac{1}{2}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.