Consider fractions ab where a and b are positive integers. (a) Prove that for every positive integer n, there exists such a fraction ab such that √n≤ab≤√n+1 and b≤√n+1. (b) Show that there are infinitely many positive integers n such that no such fraction ab satisfies √n≤ab≤√n+1 and b≤√n.
Problem
Source: 2016 IMO Shortlist A5
Tags: IMO Shortlist, algebra, Fractions, Hi
19.07.2017 20:34
19.07.2017 20:34
Write the main inequality as nb2≤a2≤(n+1)b2. We first solve part (b) by claiming that n=x2+1 always fails. For concreteness we start by giving an example with x=10: b=1 gives 101≤a2≤102. b=2 gives 404≤a2≤408. b=3 gives 909≤a2≤918. \dots b=10 gives 10100≤a2≤10200. None of these intervals contain squares, by just a little bit. In general, for any b≤x we have (bx)2<b2(x2+1)≤b2(x2+2)<(bx+1)2and so the interval [b2(x2+1),b2(x2+2)] contains no squares. As for part (a), write n=x2+r where x=⌊√n⌋. Intuitively want to select b such that (x2+r)b2≈(xb)2 is just slightly larger than a square; but we want b to be large (close to x) to give room to a. Letting a=xb+k, a good guess is (x2+r)b2≈(xb+k)2 with k not too big, meaning b2r≈2bxk, or b≈2kxr. Here is the construction: For r even, set k=r/2, hence b=x. This works, with a=x2+r/2. For r odd, set k=12(r+1), hence b=x+1. This works (and is even motivated by (b)), with a=b2+b+12(r+1). We leave the verification of these to the reader.
22.07.2017 05:09
My favorite problem among the algebra problems of this year's shortlist, though it is not hard if you have some knowledge of Farey sequences. For (a), suppose √n and √n+1 are irrational and let t=[√n]=[√n+1]≥2 (t=1 case is trivial). The problem statement is equivalent to the fact that there is a element q of Ft+1 (Farey sequence of order t+1) such that {√n}<q<{√n+1}. Suppose this is not true. Then there exist two consecutive elements q1,q2 of Ft+1 such that {√n} and {√n+1} are both included in the interval (q1,q2). Let q1=ab, q2=cd in their irreducible forms. Then q2−q1=1bd and hence 1bd>√n+1−√n=1√n+1+√n>12t+2. So bd≤2t+1 but since b+d>t+1, there are only four possibilities (b,d)=(1,t+1),(t+1,1),(t,2),(2,t) which are equivalent to (q1,q2)=(0,1t+1),(tt+1,1),(t−12t,12),(12,t+12t) respectively. It is easy to check that each of these cases is impossible. For (b), n=t2+1 for any positive integer t works since √n and √n+1 both belong in interval (0,1t), where 0 and 1t are consecutive elements of Ft.
31.07.2017 03:07
We tackle part (a) first by dealing with all integers n from s2+1 to (s+1)2 inclusive. Obviously a=b=1 works for n=1. We'll split into cases. Case 1: n=s2+2k where s is a positive integer and 1≤k≤s is an integer. We claim that a=s2+k, b=s works. Squaring both sides of the given inequality yields s2+2k≤(s2+ks)2≤s2+2k+1→s2+2ks2+k≤s2+ks2≤s2+2k+1s2+k.This inequality boils down to ks2+k≤ks2≤k+1s2+k. The left inequality is obvious, while the right inequality becomes ks2+k2≤ks2+s2 →k2≤s2, which is true because 1≤k≤s. Hence, this choice for a, b works. Case 2: n=s2+2k+1 where s is a positive integer and 0≤k≤s is an integer. We claim that a=s(s+1)+k+1, b=s+1 works. Likewise, we square both sides of the given inequality, leaving us with s2+2k+1≤(s2+s+k+1s+1)2≤s2+2k+2→s2+2k+1s2+s+k+1≤s2+s+k+1s2+2s+1≤s2+2k+2s2+s+k+1.This inequality is messier than the previous one we dealt with, but we'll use some more algebraic manipulations to verify it. The left inequality boils down to k−ss2+s+k+1≤k−ss2+2s+1. If k=s, we get 0=0, which leaves us to check s2+2s+1≥s2+s+k+1→2s≥s+k since k−s is negative from k<s. But 2s≥s+k is obvious. The right inequality boils down to k−ss2+2s+1≤k−s+1s2+s+k+1. Cross-multiplying and subtracting (k−s)(s2+2s+1) from both sides yields (k−s)2≤s2+2s+1. This becomes k2−1=(k−1)(k+1)≤2s(k+1). Since k−1≤2s, the inequality is true. So, this choice of a and b works, solving part (a). For part (b) we can just show that n=s2+1 fails. In part (a) we have established that choosing a=s2+1, b=s yields that ab is greater than or equal to √s2+2=√n+1. However, since s is a positive integer, √n+1 is irrational, and since ab is rational, it must be greater than √n+1. But then, ab=s2+1s is the smallest possible value of ab we can have given that 1≤b≤√n. So no choices of integers a, b work if n=s2+1, and we're done.
02.09.2017 16:23
I hope this gives a somewhat "less messy" solution to part (a) (without knowledge of Farey sequence). Suppose k≤√n<k+1 and write n=k2+r with 0≤r≤2k. Observe that √n−k=n−k2√n+k=r√n+k≤rk+k=r2kand √n+1−k=n−k2+1√n+1+k=r+1√n+1+k≥r+1(k+1)+k=r+12k+1.Recall the fact that x+zy+z≥xy whenever y≥x>0 and z≥0, which tells us that √n≤k+r2k≤k+r+12k+1≤√n+1If r is even, then we can cancel a common factor in the fraction r2k, so we can take the fraction ab=k+r2k. If r is odd, consider s:=(k+1)2−n=2k−r+1 (which is even whenever r is odd), and observe that (k+1)−√n=(k+1)2−n(k+1)+√n=s(k+1)+√n≥s(k+1)+(k+1)=s2(k+1)and (k+1)−√n+1=(k+1)2−n−1(k+1)+√n+1=s−1(k+1)+√n+1≤s−1(k+1)+k=s−12k+1.Again, we get √n≤(k+1)−s2(k+1)≤(k+1)−s−12k+1≤√n+1,so we can pick the fraction ab=(k+1)−s2(k+1).
09.12.2017 05:06
a) Let m=⌊√n⌋. So m+1=⌈√n+1⌉. Notice that 2|n−m2 or 2|n−(m+1)2. WLOG, let 2|n−m2 and k=n−m22. We know that km+1≤2k2m+1≤√n−m=2km+√n≤2k2m=km. Similarly for all other n, if p=(m+1)2−n2 then pm+1=2p2m+2≤(m+1)−√n=2p(m+1)+√n≤2p2m+1≤pm. Hence the fractions {m2m,m2+1m,m2+2m,…,m2+mm,m2+mm+1,m2+m+1m+1,m2+m+2m+1,…,(m+1)2m} 'partition' the squareroot of the integers {m2,m2+1,…,(m+1)2} in the order of sizes. The conclusion follow, with b=m or m+1 b) We claim that all n=m2+1 for some integer m doesn't satisfy the given condition. Suppose otherwise. We must have √m2+2≥ab>m. But ab−m≤√m2+2−m=2√m2+2+m<22m=1m so we must have b>m for the inequality to hold. Done
01.04.2020 12:16
My solution for part (b) is same as of @above , so won't repeat mathwizard888 wrote: Consider fractions ab where a and b are positive integers. (a) Prove that for every positive integer n, there exists such a fraction ab such that √n≤ab≤√n+1 and b≤√n+1. (b) Show that there are infinitely many positive integers n such that no such fraction ab satisfies √n≤ab≤√n+1 and b≤√n. Very nice problem , the main idea here is to write down many many examples Solution- Part (a)- Let S denote the set of all n for which such a,b exist , we will show that S=N, by adding numbers one by one Claim 1 - 1,2,3,4,5,6,7,8,9∈S This can easily be shown by directly taking values of a,b , this is here just to remove complications later , so hereafter we assume all values are greater than 9. Claim 2 - n2∈S This is also trivial by taking a=n,b=1 Claim 3 - n2−1∈S Again take a=n,b=1 Now we come to the non-trivial part Claim 4 - For given b and 1≤i≤2b−1 , we have (b−1)2+2i−1∈S Proof- The proof is easy in the sense that we will directly give a,b ( b is obviously b) Let ai=b2−b+i where 1≤i≤2b−1 and define xi=⌊a2ib2⌋ First we show that xi=(b−1)2+2i−1 It is easy to check that x1=(b−1)2+1,xb=b2 and x2b−1=(b−1)2+2(2b−1)−1 Now if we show that xt is an AP then we will get the required result Note that a2i+1b2−a2ib2=2+2i+1−2bb2 So for 1≤i<b we have a2i+1b2−a2ib2≤2⟹xi+1−xi≤2 Now we simply add everything to get 2b−2=xb−x1=(xb−xb−1)+⋯+(x2−x1)≤2(b−1)=2b−2 Hence equality must hold everywhere and similarly we do for b≤i≤2b−1 but with the sign flipped to get that xi is an AP. And as there is only one AP of given lenght and fixed endpoints we get that xi=(b−1)2+2i−1 Now if we show that all xi∈S then we will be done First note that √xi≤aib≤√xi+1 So its enough to show that b≤√xi+1 but note that xi is increasing and b=b−1+1<√(b−1)2+1+1=√x1+1 and hence we are done. Main Proof- Now we show that we have covered all natural numbers. Let n∈N be given , if n is a perfect square we are done by claim 2. So let k2<n<(k+1)2 , now we make two casses- Case I - n and k have same parity Let n−(k−1)2=2i−1 we have 2i−1<(k+1)2−(k−1)2⟹i≤2k If i=2k then n=(k+1)2−1 and we use claim 3 If i≤2k−1 we use claim 4 with b=k Case II - n and k have different parity Let n−k2=2i−1 then 2i−1<2k+1⟹i<k+1<2(k+1)−1 Hence we are done using claim 4 with m=k+1. Hence proved!!!!!!!
18.07.2020 23:46
Let k=⌊√n⌋. We claim that for any 0≤q≤k, k+qk+1∈[√k2+2q−1,√k2+2q],k+qk∈[√k2+2q,√k2+2q+1],which would solve part (a). Both follow by squaring: for the latter, we want to show k2+2q≤(k+qk)2≤k2+2q+1, which is clear since the middle expression is k2+2q+q2k2. For the former, we want to show k2+2q−1≤(k+qk+1)2≤k2+2q, which is also easy to verify by expansion. For part (b), we claim we can choose n=k2+1 for any k≥1. Suppose there exists some ab with b≤k such that √k2+1≤ab≤√k2+2. But k+1k≥√k2+2 (which follows directly from squaring), contradiction.
11.09.2020 00:14
Part a) Solution: Call a number n hot if there exists a fraction ab satisfying the problem. Partition the positive integers into intervals of the form [k2,(k+1)2−1] as k ranges from 1→∞. We will prove that for any arbitrary interval [k2,(k+1)2−1], all numbers in it are hot. Notice that in this range, we require b≤k+1. For n of the form k2+2i, where i:0→k, we may select ab=k+ik. Indeed, we may check thatk2+2i≤(k+ik)2=k2+2i+i2k2≤k2+2i+1as desired. For n of the form k2+2i−1, where i:1→k, we may select ab=k+ik+1. Indeed, we may check thatk2+2i−1≤k2+2i−(2ik+1−i2(k+1)2)=(k+ik+1)2≤k2+2ias desired. Hence all n in each interval [k2,(k+1)2−1] are hot, and considering all intervals, we are done. ◼ Part b) Solution: I claim that all n=k2+1 work for large enough k. Let x be an integer and suppose√x2+1≤ab≤√x2+2for some rational ab with b≤x. Squaring and multiplying by b2, we get b2(x2+1)≤a2≤b2(x2+2). Clearly, the LHS of this bound satisfies b2(x2+1)>(bx)2. Less clearly, the RHS of the bound satisfiesb2(x2+2)=b2x2+2b2≤b2x2+2bx<(bx+1)2so in fact, the perfect square a2 is strictly bounded between two consecutive squares, a contradiction. ◼
07.12.2020 03:45
Beautiful problem. The key idea is to consider blocks m2,m2+1,…,m2+2m for positive integers m in which any n falls. The following diagram reveals what is going on. (01/31/21/3101/41/32/42/33/4101/51/42/52/43/53/44/51). For n=m2 take a/b=m/1. For n=m2+2m take a/b=(m+1)/1. For n=m2+1,…,m2+2m−1, let c=((m+1)2−n)/2. Then (m+1−cm+1)2=m2+2m+1−2c+c2(m+1)2,so a/b=m+1−c/(m+1) works. For n=m2+2,…,m2+2m−2, let c=(n−m2)/2. Then (m+cm)2=m2+2c+c2m2,so a/b=m+c/m works. This resolves part a. For part b, note that m2+1 must be one such example because (m+1/m)2>m2+2, so for any b≤m, a2/b2>m2+2 or a2/b2≤m2.
23.02.2021 00:57
We first solve (a). Let n=m2+k where 0≤k≤2m. If k is even, select b=m and a=m2+k2. Note that √n≤ab≤√n+1⟺b2n≤a2≤b2(n+1)⟺m2(m2+k)≤m2+m2k+k24≤m2(m2+k+1)⟺0≤k2≤4m2⟺0≤k≤2m,which is true. If k is odd, let b=m+1 and a=m(m+1)+k+12. In that case, we have √n≤ab≤√n+1⟺b2n≤a2≤b2(n+1)⟺(m+1)2(m2+k)≤m2(m+1)2+m(m+1)(k+1)+(k+1)24≤(m+1)2(m2+k+1)⟺k(m+1)2≤m(m+1)(k+1)+(k+1)24≤(k+1)(m+1)2⟺(k−m)(m+1)≤(k+1)24≤(k+1)(m+1).Both of these are easy to verify, so we're done. For (b), let n=m2+1. Then, we need to show that [b√m2+1,b√m2+2]contains no integers. It is enough to show that b√m2+2<bm+1. Note that b√m2+2<bm+1⟺b2m2+2b2<b2m2+2bm+1⟺2b(m−b)+1>0,which is true as b≤m. This completes the solution.
01.06.2021 10:02
dame dame
05.01.2022 05:21
Write n as k2+m where k=⌊√n⌋. Then, note that in (a) we can select any b≤k+1 . Case 1: k2+2x, note that x≤k. Then, the selection of ab=k+1k works because (k+xk)2=k2+2x+x2k2∈[k2+2x,k2+2x+1] Case 2: k2+2x−1. Note that 1≤x≤k. Then, (k+xk+1)2=k2+2xk2+2xk+x2(k+1)2AFTSOC that 2xk2+2xk+x2>2x(k+1)2=2xk2+4xk+2x⟹x2−2x>2xk≥2x2 which is clearly absurd.Thus ab2≤k2+2x. Next, note that 2kxk+1≥2x2x+1≥2x−1, so ab2≥k2+2kxx+1+x2(k+1)2≥k2+2k−1+x2(k+1)2. Thus, we have shown that ab∈[k2+2x−1,k2+2x] and we are done with part a. For part b, note that n=k2+1 works. Since b≤k, if ab≥k, then ab≥k+1k, but (k+1k)2=k2+2+1k2>k2+2=n+1, a failure. Thus, all n of the form k2+1 fail, and we clearly have infinitely many valid choices of n and part (b) is done.
02.02.2022 17:40
First we solve part (a). Fix n and assume contrary. Let ⌊n⌋=k. Case k=1 is easy. Assume k≥2. Let S be set of all fractions with denominator ≤k+1. Choose ab,cd∈S such that ab<√n≤√n+1<cd(1)and the interval (ab,cd) contains no fraction of S. As a+cb+d∈(ab,cd), thus b+d≥k+2. Claim: bc−ad=1. Proof: Our Claim just follows by Farey sequences.◻ Using our claim we obtain 12(k+1)<1√n+1+√n=√n+1−√n<cd−ab=bc−adbd=1bd⟹bd≤2k+1(2)Now recall that b+d≥k+2. Claim: min. Proof: Assume contrary that b,d \ge 3. Then (b-3)(d-3) \ge 0 \implies bd \ge 3(k-1). So k \le 4. Now if b+d \ge k+3, then bd \ge 3k, giving k \le 1, contradiction. If b+d = k+2, then that forces b=d=3,k=4. But that contradicts \gcd(b,d) = 1 (which follows from bc - ad = 1). \square Now we have several cases. Main idea in each of them is to bound \frac{c}{d} - \frac{a}{b}. Case 1.1: b=2. Then (2) forces d=k and (1) forces a= 2k+1. Then n > k^2+ k forcing \sqrt{n+1} \ge \sqrt{k^2 + k + 2}. Then, \begin{align*} \frac{1}{2k} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \sqrt{n+1} - \frac{a}{b} \ge \sqrt{k^2 + k +2} - \frac{2k+1}{2} = \frac{\frac{7}{4}}{ \sqrt{k^2 + k + 2} + \frac{2k+1}{2}} \\ \implies \sqrt{k^2 + k + 2} + \frac{2k + 1}{2} \ge \frac{7}{2} \cdot k \implies \sqrt{k^2 +k + 1} \ge k + 1 \end{align*}Case 1.2: d=2. Then 2 forces b = k and (1) forces c=2k+1. Now n+1 \le k^2 + k forcing \sqrt{n} \le k^2 + k -1. Then, \begin{align*} \frac{1}{2k} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \frac{c}{d} - \sqrt{n} \ge \frac{2k + 1}{2} - \sqrt{k^2 + k -1} = \frac{ \frac{5}{4}}{ \frac{2k + 1}{2} + \sqrt{k^2 + k -1}} \\ \implies \frac{2k+1}{2} + \sqrt{k^2 + k - 1} \ge \frac{5}{2} \cdot k \implies \sqrt{k^2 + k -1} \ge k + \frac{1}{2} \end{align*}Case 2.1: b=1. Then d \le k+1 and b +d \ge k+2 forces d = k+1. Also (1) gives a=k. Now n > k forcing \sqrt{n+1} \ge \sqrt{k^2+2}. Thus, \begin{align*} \frac{1}{k+1} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \sqrt{n+1} - \frac{a}{b} \ge \sqrt{k^2 + 2} - k = \frac{2}{\sqrt{k^2 + 2} + k } \\ \implies \sqrt{k^2 + 2} + k \ge 2(k+1) \implies \sqrt{k^2 + 2} \ge k + 2 \end{align*}Case 2.2: d=1. Then b \le k+1 and b+d \ge k+2 forces b = 2k+1. Also (1) gives c=k+1. Now n+1 < k+1 forcing \sqrt{n} \le \sqrt{k^2 - 2}. Thus, \begin{align*} \frac{1}{k+1} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > k + 1 - \sqrt{(k+1)^2 - 2} = \frac{2}{k + 1 + \sqrt{(k+1)^2 - 2}} \\ \implies k+1 + \sqrt{(k+1)^2 - 2} \ge 2(k+1) \implies \sqrt{(k+1)^2 - 2} \ge k+1 \end{align*}In each case, we obtain a contradiction. This solves (a). Now we solve (b). Take n = t^2 - 2 for any t \ge 2. We will prove no such \frac{a}{b} exists. Suppose not and write \sqrt{t^2 - 2} \le \frac{a}{b} \le \sqrt{t^2 - 1} By assumption b \le t-1. Now \frac{a}{b} < t gives \frac{a}{b} \le \frac{tb - 1}{b} = t - \frac{1}{b} \le t - \frac{1}{t-1} Using \sqrt{t^2 - 2} \le \frac{a}{b} we obtain \begin{align*} \frac{1}{t-1} \le t - \sqrt{t^2-2} = \frac{2}{t + \sqrt{t^2 - 2} } \end{align*}This is a contradiction, completing the proof. \blacksquare
12.05.2023 22:30
24.05.2023 23:14
Let n=x^2+y where 0\le y\le 2x. Note that \lfloor \sqrt{n} \rfloor = x. Note that 0 \le \tfrac{y^2}{(2x)^2} \le 1. Thus, if y is even then we have \sqrt{n} = \sqrt{x^2+y}\le \sqrt{x^2+y+\frac{y^2}{(2x)^2}} = \sqrt{\left(x+\frac{y}{2x}\right)^2} = \frac{x^2+\frac{y}{2}}{x} \le \sqrt{x^2+y+1} = \sqrt{n+1}If y is odd then pick a=x(x+1)+y+1 and b=x+1. The calculations work out and are long to type out so I'll omit them. We prove that we cannot find b\le \sqrt{n} for n=x^2+1. Note that if a rational number exists, it must be between x and x+1 exclusive. The smallest such number is \tfrac{x^2+1}{x} which is still too big.
10.08.2023 02:04
We are essentially being asked to prove that there always exists an integer in the range [b\sqrt{n},b\sqrt{n+1}], or equivalently in the range [b\{\sqrt{n}\},b\{\sqrt{n+1}\}], or equivalently a square in the range [b^2n,b^2(n+1)], for some b \leq \sqrt{n}+1, but not always for some b \leq \sqrt{n}. For part (a), write n=p^2+q where p is maximal. Then, If q is even, take b=p. Then p^2(p^2+q)\leq\left(p+\frac{q}{2}\right)^2 \leq p^2(p^2+q+1),where the first inequality is obvious, and the second inequality is equivalent to 2p \geq q, which is true. If q is odd, take b=p+1. Then note that (p^2+2p+1)(p^2+q)=\left(p^2+p+\frac{q+1}{2}\right)^2-\left(p+\frac{1-q}{2}\right)^2\leq \left(p^2+p+\frac{q+1}{2}\right)^2,and therefore (p^2+2p+1)(p^2+q)=\left(p^2+p+\frac{q+1}{2}\right)^2-\left(p+\frac{1-q}{2}\right)^2+(p+1)^2 \geq \left(p^2+p+\frac{q+1}{2}\right)^2,which is true since 0 \leq p+\tfrac{1-q}{2} \leq p+1. For part (b), I claim that n=k^2+2 fails where k is a large positive integer. We have \{\sqrt{n+1}\}=\sqrt{k^2+2}-k=\frac{2}{k^2+\sqrt{k^2+2}}<\frac{1}{k},hence the interval [b\{\sqrt{n}\},b\{\sqrt{n+1}\}], which is always positive, is also always less than 1 for b \leq \sqrt{n}, hence it never contains an integer when b \leq \sqrt{n}.
27.12.2023 20:37
We rephrase the problem as follows: given a fixed integer m, there must exist fractions \frac ab with b \leq m + 1 such that \frac k{m+\sqrt{m^2+k}} \leq \frac ab \leq \frac{k+1}{m+\sqrt{m^2+(k+1)}}.This is equivalent to the original problem through setting m = \lfloor \sqrt n \rfloor. The key claim is the following: Claim. For every k \leq m, we have \frac{2k-1}{m+\sqrt{m^2+2k-1}} \leq \frac k{m+1} \leq \frac{2k}{m+\sqrt{m^2+2k}} \leq \frac km \leq \frac{2k+1}{m+\sqrt{m^2+2k+1}}. Proof. The middle two inequalities follow easily by noting m < \sqrt{m^2+2k} < m+1. The right inequality rewrites as \begin{align*} k\sqrt{2k+km+1} &\leq km + m \\ \iff 2k^3+k^2+m^2+k^2 &\leq k^2m^2+m^2+2km^2 \\ \iff (m^2-k^2)(2k+1) &\geq 0. \end{align*}This is clear as we always have k \leq m. The left inequality rewrites as \begin{align*} km +k\sqrt{m^2+2k-1} &\geq 2km - m + 2k - 1\\ k^2m^2+2k^3-k^2 &\geq (km-m+2k-1)^2 \\ (2k-1)(k-m-1)^2 &\geq 0 \end{align*}which is obviously true. Hence the claim is proved. \blacksquare This implies that we can satisfy all the constraints by only picking fractions with b = m or b = m+1, which finishes the first part. For the second part, taking n = m^2+1, notice that \frac 1m > \frac 2{m+\sqrt{m^2+2}}, so there is no fraction with b \leq m in the range [\sqrt n, \sqrt{n+1}], so the bound is tight.
19.02.2024 13:30
Nice and straightforward. (a) Suppose for contradiction that there is a positive integer n for which there doesn't exist a fraction satisfying our condition. It is easy to check the cases where n < 9, so assume that n \geq 9. We may assume that \sqrt{n} is irrational since otherwise, we can simply pick a=n and b=1. Let \frac{a}{b} be the largest fraction (in irreducible form) not exceeding \sqrt{n} such that b \leq \sqrt{n}+1. Choose the largest positive integer y such that ay \equiv -1 \pmod{b} and y \leq \sqrt{n}+1, and let x = \frac{ay+1}{b}. Note that b+y \geq \sqrt{n}+1, which implies that b+y \geq \lfloor \sqrt{n} \rfloor + 2. We have \frac{x}{y}-\frac{a}{b}=\frac{xb-ay}{by} = \frac{1}{by}. Therefore, by assumption we must have \frac{1}{by} \geq \sqrt{n+1} - \sqrt{n} = \frac{1}{\sqrt{n}+\sqrt{n+1}} which implies that by \leq \sqrt{n}+\sqrt{n+1} < 2\lfloor \sqrt{n} \rfloor+2. Suppose that b \geq 3. Then by AM-GM we get by \geq 3 (\lfloor \sqrt{n} \rfloor-1) \geq 2 \lfloor \sqrt{n} \rfloor + 2, a contradiction. Let n = x^2 + c. Case 1: b=1. Since \frac{a}{1} is the largest rational number with b \leq \sqrt{n}+1 not exceeding \sqrt{n}, we must have \sqrt{n} \leq x + \frac{1}{x+1} \implies n \leq x^2 + \frac{2x}{x+1}+\frac{1}{x^2+2x+1}< x^2+2 \implies c = 1. Then it is not hard to check that \sqrt{x^2+1} \leq \frac{x^2+x+1}{x+1} \leq \sqrt{x^2+2} always holds. \square Case 2: b=2. Since \frac{a}{2} is the largest rational number with b \leq \sqrt{n}+1 not exceeding \sqrt{n}, we must have x + \frac{1}{2} \leq \sqrt{x^2+c} \leq x + \frac{1}{2} + \frac{1}{2x}. Squaring this inequality we get x^2+x < (x + \frac{1}{2})^2 \leq x^2+c \leq (x+\frac{1}{2} + \frac{1}{2x})^2 < x^2+x+2. This implies that c=x+1. Then it is not hard to check \sqrt{x^2+x+1} \leq x + \frac{x+2}{2(x+1)} \leq x + \frac{x+1}{2x} \leq \sqrt{x^2+x+2} always holds. \blacksquare (b) Looking at Case 1 from part (a), we observe that our bound barely holds. So we may presume that x^2+1 works. Indeed, it is very simple to show that we have x + \frac{a}{b} \geq \sqrt{x^2+2} for all fractions with b \leq \sqrt{n}. \blacksquare
03.05.2024 11:38
Woah, one of the coolest algebra problems ever For part a, let k = \left\lfloor \sqrt n \right\rfloor. Then, we can manually check the cases k < 5. for k \geq 5, the cases where n or n+1 are perfect squares are clear. Also, if n = k^2+k, then, k+\frac{1}{2} lies between \sqrt{n} and \sqrt{n+1}. Consider the Farey sequence of order k+2. So, now it is a well known property of Farey sequences that if \frac{a_i}{b_i} and \frac{a_{i+1}}{b_{i+1}}, then a_{i+1}b_i-a_ib_{i+1} = 1 and b_i+b_{i+1} \geq k+2. Now, it is clear that no fraction with denominator 1 or 2 lies between \sqrt{n} and \sqrt{n+1} (as we already handled such cases in the last paragraph). But, \sqrt{n+1}-\sqrt{n} = \frac{1}{\sqrt{n+1}+\sqrt{n}} > \frac{1}{2k+2}Also, \frac{a_{i+1}}{b_{i+1}}-\frac{a_i}{b_i} = \frac{a_{i+1}b_i-a_ib_{i+1}}{b_ib_{i+1}} = \frac{1}{b_ib_{i+1}} \leq \frac{1}{3k-3}For k > 5, the difference between \sqrt{n+1} and \sqrt{n} is more than that of consecutive terms of the Farey sequence, so one term of the sequence lies between the radicals, and we are done For the second part, if n = k^2+1, then, note that \sqrt{n}-k \leq \frac{a}{b}-k \leq \sqrt{n+1}-k and the fraction in the middle is between 0 and 1, so it is atleast \frac{1}{k}, but we can see \sqrt{k^2+2}-k = \frac{2}{\sqrt{k^2+2}+k} < \frac{1}{k}, so we are done.
06.12.2024 22:56
(a) We consider two cases: If n = x^2 + 2k, where x = \lfloor \sqrt{n} \rfloor, it follows that n = x^2 + k \leq x^2 + k +\left( \frac{k}{x} \right)^2 \leq x^2 + k + 1 = n + 1. Thus, \sqrt{n} \leq \frac{x^2+k}{x} \leq \sqrt{n+1}. If n = x^2 + 2k + 1, where x = \lfloor \sqrt{n} \rfloor, it follows that n = x^2 + 2k = (x+1)^2 - 2(x-k) < (x+1)^2 - 2(x-k) + \left( \frac{x-k}{x+1} \right)^2. < (x+1)^2 - 2(x-k) + 1 = x^2 + 2k + 1 = n+1. Thus, \sqrt{n} < \frac{(x+1)^2 + (x-k)}{x+1} < \sqrt{n+1}. (b) Suppose n = x^2 + 1 and that there exist a, b satisfying the problem. It follows that (bx)^2<b^2(x^2 + 1) \leq a^2 \leq b^2(x^2 + 2) < bx^2 + 2bx < (bx+1)^2 This leads to a contradiction.