This was an exceptionally silly problem. Just adapt the solution by math154 here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2374845&sid=1239d79b028d1d68c485fa16a00de1ad#p2374845

Did other people's proofs involve showing that the sum of the reciprocals of the squares of the primes is less than 1/2?

I would not call the problem itself silly, I think it's actually quite nice. BUT, the situation is silly, indeed: I was unaware of the problem you are indicating in the link and was very happy when I discovered this property. This is a real nightmare. I still wonder however why the other people did not realize that this problem appeared before…

I did it differently and I am not sure I am correct. Outline: I first proved that one member of each of the sets (a+i and b+j) was divisible by at least n distinct primes, and with some slight adjustments you can bound the min(a,b) by the product of the first n primes, which you can further bound with the prime number theorem for sufficiently large n and with a teensy bit more work you're good.

I showed it was less than 3/5 Note: I didn't actually complete the proof though

Yes, it pretty much involved showing sum of 1/p^2 is less than 1/2, if you tried to count number of primes greater than n.

@v_enhance if I show that it's sufficient to have 26% at least n but don't actually prove this, do you think it could be worth a point?

harazi wrote: I would not call the problem itself silly, I think it's actually quite nice. BUT, the situation is god - silly, indeed: I was unaware of the problem you are indicating in the link and was very happy when I discovered this property. This is a real nightmare. I still wonder however why the other people did not realize that this problem appeared before… harazi, is this your problem? If so, congratulations on getting another problem on the USAMO -- shame that it's appeared somewhere else, but there's so many problems out there that nothing can be done about it, so IMHO you should just take it as a compliment that both times the problem selectors liked the idea. I'm curious, do you know whether the asymptotic bound can be improved easily? pi37 wrote: @v_enhance if I show that it's sufficient to have 26% at least n but don't actually prove this, do you think it could be worth a point? My guess would be yes, but it's hard to tell.

I might be really off but I managed to prove an asymptotic bound of $c^nn^n$ for some pretty small c.

^how did you so so?

I don't know what he did but my method works for any exponent of n on the rhs of the inequality that is smaller than n, so to speak, so that bound seems right to me

Ok here is my solution which I think is slightly stronger than most of the above solutions:

Also if anyone would be willing to answer a question about grading, suppose I gave the above solution but instead of

I said

how many points would this get? Would it more likely be 7- or 0+? Thanks.

^ since by prime number theorem pi(n) ~ n/ln(n), you cannot infer that (which seems to be the necessary step you're implying) pi(n) < O(ln(n)) since that implies n< O(ln(n)^2); correct statement but wrong "proof". Hopefully that will probably be a 7- because it can be overlooked.

@james4l: wait what are you defining q to be? It seems that on one hand it came from the collection of the 1's in (m/p+1)^2, but you also define it to be the number of distinct primes dividing some a+i; those are not necessarily equivalent because by using the algebraic expansion, you seem to assume every prime above n divides a+i for some i. Edit: never mind, you're using only primes that divide a+i in (m/p+1)^2.

james4l's solution is effectively identical to math154's argument in the other thread so its definitely correct. You can actually bound $q$ to me approximately $0.54n^2 + O(n \log \log n)$ (james4l's solution did not state $q < n^2$, otherwise you can't bound the term of $\sum \frac{1}{p}$ as $(O(\log \log n))$ as if $q$ were say $e^n$ things would be bad). So then we can work with the product of the approximately first $0.54n^2$ primes, which equals $e^{(1 + o(1))k \log k}$, gets us a bound of roughly $n^{1.08n^2 (\log n + \frac{1}{2}\log 0.54)}$ on $(a+n)^n$. Unfortunately multiplicity is a bit hard to account for so I don't think we can really improve the bound using (1).

james4l wrote: (1/2^2+1/3^2+1/5^2+...) < 1/2, as (1/1^2+1/2^2+1/3^2+...) = pi^2/6 < 10/6 (1/2^2+1/3^2+1/4^2+...) < 4/6 Then take out all evens larger than 2 to get 3/6 or 1/2. [/hide] Can not take out all evens larger than 2 to get 3/6.

yunxiu wrote: james4l wrote: (1/2^2+1/3^2+1/5^2+...) < 1/2, as (1/1^2+1/2^2+1/3^2+...) = pi^2/6 < 10/6 (1/2^2+1/3^2+1/4^2+...) < 4/6 Then take out all evens larger than 2 to get 3/6 or 1/2. [/hide] Can not take out all evens larger than 2 to get 3/6. Well actually, all the evens larger than 2 would sum to $\dfrac{1}{4}\left(\frac{\pi^2}{6}-1\right)$, so taking them out would give you $\dfrac{\pi^2}{8}-\dfrac{3}{4}<\dfrac{10}{8}-\dfrac{3}{4}=1/2$ so it works.

I found that the official solution did not use the prime number theorem $\frac{\pi(n)}{n} \sim \frac{1}{\ln n}$. If we use this, I proved the bound $n^{n^2}$ and I did not find any errors. Is it right?

To simplify computation, we only use $i,j\in\{1,\ldots,n\}$. We will prove the stronger bound $\min\{a,b\}>(cn)^n$ for sufficiently large $n$. Let $\varepsilon=10^{-10}$ be small. Consider the $n\times n$ grid defined by the points $(a+i,b+j)$ where $i,j\in\{1,\ldots,n\}$, and in each cell place the least prime factor of $\gcd(a+i,b+j)$. Note that each prime $p$ divides at most $(1+n/p)^2$ cells of the grid. Claim: For $n$ large, at most $n^2/2$ of the cells of the grid contain a prime $p<\varepsilon n^2$. Proof. The number of primes covered is \[ \sum_{p<\varepsilon n^2}\left(1+\frac np\right) \le\pi(\varepsilon n^2)+2n\sum_{p<\varepsilon n^2}\frac1n+n^2\sum_{p<n}\frac1{p^2} <\frac{n^2}2 \]for sufficiently large $n$. $\blacksquare$ Hence for some $i$, the row $a+i$ contains at least $n/2$ primes $p\ge \varepsilon n^2$. For $n>\varepsilon^{-1}$, none of the primes divide two numbers of the form $b+j$, so these $n/2$ primes are all distinct. Then \[(a+i)^n>(\varepsilon n^2)^{n/2}=\varepsilon^{n/2}\cdot n^n,\]as needed. Remark: Some more details on the estimates: where $s=\varepsilon n^2$, we have \begin{align*} \pi(s)&=\frac s{\log s}\left(1+O\left(\frac1{\log s}\right)\right)=o\left(n^2\right)\\ \sum_{p<s}\frac1p&<\sum_{k=1}^s\frac1p=O(\log s)=o(n^2)\\ \sum_{p<s}\frac1{p^2}&<\sum_p\frac1{p^2}\approx0.452<\frac12. \end{align*}For curiosity sake, the best bound for the second expression is $\sum_{p<s}\frac1p=\log\log s\cdot(1+o(1))$. Remark: Here is an easy proof of $\sum_p\frac1{p^2}<\frac12$. Note that \[\sum_{n\text{ odd}}\frac1{n^2}=\sum_n\frac1{n^2}-\sum_{n\text{ even}}\frac1{n^2}=\frac34\cdot\frac{\pi^2}6<\frac54\]by $\pi^2<10$. Then \[\sum_p\frac1{p^2}<-\frac1{1^2}+\frac1{2^2}+\sum_{n\text{ odd}}\frac1{n^2}<\frac12.\] Remark: We prove $\min\{a,b\}>(cn)^n$ instead. The requested bound $(cn)^{n/2}$ is derived by proving primes $p<n$ cover at most $n^2/2$ cells, and using that estimate instead.

I found a slightly different approach with the aid of Wikipedia. Let $p_1<p_2<\cdots <p_k$ denote the first $k$ primes and suppose that for any pair of $i,j$, some $p_\ell$ divides $\gcd(a+i,b+j)$. Clearly it is possible to choose some minimal $k$ satisfying this property. Then observe that \[n^2\le \sum_\ell \left\lceil\frac{n}{p_\ell}\right\rceil^2 < n^2\sum_\ell \frac{1}{p_\ell^2}+2n\sum_\ell \frac{1}{p_\ell} +k.\]It is well-known that \[\sum_{p\mbox{ is a prime}}\frac{1}{p^2} < 0.46.\]Thus we have \[0.54n^2<2n\sum_\ell \frac{1}{p_\ell} +k.\]Observe the bound \[\sum_\ell \frac{1}{p_\ell} \le \sum_\ell\frac{1}{\ell+1} = O(\log k).\]Since the case $k=1$ is clearly a small case, we can disregard it so the expression is at most $\log k$. Then we have \[0.54<\frac{O(\log k)}{n}+\frac{k}{n^2}.\]This expression is increasing as $k$ increases, so since $k=n^2/2$ does not satisfy this inequality asymptotically, this implies $k>n^2/2$ asymptotically. Remark that \[a(a+1)\cdots (a+n)\ge \prod_\ell p_\ell\implies \sqrt[n]{\prod_\ell p_\ell} - n.\]Then it suffices to show that for some constant $c$, we have \[\prod_{\ell\le n^2/2}p_\ell \ge c^{n^2}n^{n^2/2}.\]But this is clear because $\prod_{\ell\ge n^2/2}p_\ell\ge (n^2/2)!\ge c(n^2/2)^{n^2/2}$. In fact, this would yield the stronger bound of $c^{n^2}n^{n^2}$.

Choose $n$ very large, and for each pair $(i, j)$ assign it the least prime $p_{i, j}$ dividing $\gcd(a + i, b+ j)$. Note that if a prime $p$ is assigned to some $(i, j)$, then it cannot be assigned to any $(i + \ell_1, j + \ell_2)$ where $p \nmid \ell_1, \ell_2$. So in some sense, if we create a grid of $(i,j)$ values, no two squares a distance of $< p$ apart can be occupied by prime $p$. So indeed, for each prime in the grid, a maximum of\[\left\lceil \frac{n+1}{p}\right\rceil^2 \leq \left(\frac{n+1}{p} + 1\right)^2\]squares (representing the $p_{i, j}$ values) can be $p$. The claim is that $\geq \tfrac{(n+1)^2}{2}$ of the total $(n+1)^2$ primes exceeds $\epsilon n^2$ for some tiny constant $\epsilon$. Indeed, suppose this were not the case. Consider the extremely loose bound as we sum over all primes $p \leq \epsilon n^2$, say we call these primes tiny:\begin{align*}\text{\#squares assigned to tiny primes} &\leq \sum \left(\frac{n+1}{p} + 1\right)^2\\&= \left[(n+1)^2 \sum \frac{1}{p^2}\right] + \left[2(n+1) \sum \frac 1p \right] + \left[\epsilon n^2\right]\end{align*}It suffices to show this is $< \tfrac{(n + 1)^2}{2}$ through bounding. First, bound\[\sum_{p \leq \epsilon n^2} \frac{1}{p^2}\leq \left(\sum_{k = 2}^{\infty} \frac{1}{k^2}\right) - \left(\sum_{c \text{ composite}} \frac{1}{c^2}\right) \leq 0.49\]which can be manually checked by using the $\tfrac{\pi^2}{6} - 1$ fact and subtracting enough $\tfrac{1}{c^2}$ (say, up to $\tfrac{1}{30^2}$). Next, by loose bounding,\[\sum_{p \leq \epsilon n^2} \frac{1}{p} \leq \int_1^{\epsilon n^2} \frac 1n dn = \ln(\epsilon n^2) \implies 2(n+1) \sum \frac 1p \leq 4(n+1)\ln(\sqrt{\epsilon}n)\]but since $O(n\ln(n)) << O(n^2)$ for large enough $n$, this term is too small to matter. Thus, the total sum is upper bounded by\[0.49(n+1)^2 + C\ln(n\ln(n)) + \epsilon n^2\]which must clearly be $\leq \tfrac{(n+1)^2}{2}$ for sufficiently large $n$ and $0 < \epsilon << 0.1$. So indeed, more than half of the entries are primes $> \epsilon n^2$, for say, $\epsilon = 10^{-6}$. WLOG $a \leq b$. Then by Pigeonhole, some row/column of entries $p_{i, 0}, p_{i, 1}, \ldots , p_{i, n}$ has half of elements exceeding $\epsilon n^2$. No two of these large primes are the same since they are large, much larger than $n$, hence\[a + i \geq \prod_{p_{i, \ell} \geq \epsilon n^2} p_{i, \ell} \geq (\epsilon n^2)^{\tfrac{n+1}{2}} \geq Cn^{n+1} \implies a \geq Cn^{n+1} - n > C'n^n\]for some constant $C$ most likely around $\epsilon^{\tfrac{n+1}{2}}$, and indeed we are done. $\blacksquare$

This sounds dumb but quick question what does that small e mean? Is it the same as $e=2.71828183$ or is it something else?

$\epsilon$ is not the same as $e$ $-$ in general, choosing small $\epsilon$ just means selecting a value super close to $0$ (that satisfies what we want it to in order to make the solution work)

..........

We prove a bound for $(cn)^n.$ It suffices to show a $c$ exists working for any sufficiently large $n$ (for the finitely many $n$ left, we can choose a sufficiently small constant that will make the RHS $<1,$ then take it over $c$ if it is smaller). First, note $$\sum_{p} \frac{1}{p^2} < \frac{\pi^2}{6} - \frac{1}{1^2} - \frac{1}{2^2} \left( \frac{\pi^2}{6} - 1 \right) = \frac{\pi^2}{8} - \frac{3}{4} < \frac{10}{8} - \frac{3}{4} = \frac{1}{2}. $$Make a $(n+1) \times (n+1)$ grid. Number the rows from $0$ to $n$ from bottom to top and number the columns $0$ to $n$ from left to right. Put a prime dividing $\gcd(a+i,b+j)$ in the $i$th row and $j$th column. Let $K = dn^2$ for a constant $d,$ and suppose $n$ is sufficiently large so $K > n.$ For some constant $\epsilon > 0,$ the number of primes $< K$ appearing in the grid is at most $$\sum_{p < K} \left \lceil \frac{n}{p} \right \rceil^2 < \sum_{p < K} \left( \frac{n}{p} + 1 \right)^2 = n^2 \sum_{p < K} \frac{1}{p^2} +2n \sum_{p < K} \frac{1}{p}+ \sum_{p < K} 1 < \left(\frac{1}{2} - \epsilon \right)n^2 +2n\ln(K) + K $$which will be $< \frac{1}{2} n^2$ for all $n$ if we choose $d$ small enough. Once we've set $d,$ at least half the primes in the grid are $> K,$ so at least one row $i$ has at least $\frac{n}{2}$ of its primes $> K$ by PHP. Each such prime appears at most once in that row since $K > n.$ So $a+i$ is divisible by at least $\frac{n}{2}$ distinct primes, all greater than $dn^2,$ so $a+i > (dn^2)^{\frac{n}{2}} \implies a > (\sqrt{d}n)^n - n.$ Thus making $c$ slightly smaller than $(\sqrt{d})^{n}$ is enough. $\square$

Assume $n$ large. Let $f(i,j)$ be a prime number dividing both $a+i,b+j$. Claim: The set $S = \{f(i,j) : 0 \le i,j \le n \}$ has at least $\frac{n(n+1)}{2}$ elements. Proof: For any prime $p$, note that number of appearances of $p$ in $S$ is at most $$ \left( \left\lfloor \frac{n}{p} \right\rfloor + 1 \right)^2 $$Since multiset $S$ has $(n+1)^2$ elements, hence \begin{align*} (n+1)^2 &\le \sum_{p \in S} \left( \left\lfloor \frac{n}{p} \right\rfloor + 1 \right)^2 = \sum_{p \in S} \left( \left\lfloor \frac{n}{p} \right\rfloor ^2 + 2 \left\lfloor \frac{n}{p} \right\rfloor + 1 \right) \le \sum_{p \text{ prime}} \frac{n^2}{p^2} + \sum_{ 2 \le p \le n} \frac{2n}{p} + |S| \end{align*}Now using the facts that \begin{align*} \sum_{p \text{ prime}} \frac{1}{p^2} < \frac{1}{2} ~~,~~ \sum_{2 \le p \le n} \frac{1}{p} = O( \log n) \end{align*}our claim follows. $\square$ From our claim, it follows for some $0 \le i \le n$, the set $$ \{ f(i,0),f(i,1),\ldots,f(i,n) \} $$has at least $\frac{n}{2}$ distinct elements. Thus, $$ a + n \ge a+i \ge \left( \left\lceil \frac{n}{2} \right\rceil \right)! $$Since $$ m! \text{ grows as fast as } \left( \frac{m}{e} \right)^m$$so we are done. $\blacksquare$

We show that such a constant $c$ exists for sufficiently large $n$, taking the minimum of which with all smaller $n$ gives the desired result. Claim: It is impossible to cover half of or more of the $(n + 1) \times (n + 1)$ grid with primes less than $x = \varepsilon n^2$ for a sufficiently small $\varepsilon$ independent of $n$. Proof. Let $p$ represent primes. Then, \begin{align*} &\sum_{p \le x} \left\lceil \frac{n+1}{p} \right\rceil^2 \le \sum_{p \le x} \frac{(n+1)^2}{p^2} + 2 \cdot \frac{n+1}{p} + 1 \le \\ &0.499 (n + 1)^2 + 2 \cdot (n+1) \log x + x + O(n) \end{align*}which for sufficiently small $\varepsilon$ has $n^2$ coefficient less than one $\frac{1}{2}$. $\blacksquare$ Then, take $n$ large enough such that $\varepsilon n^2 > n$. By pigeonhole it follows that for some $a + i$ and $b + j$, they have at least $\frac{n}{2}$ prime divisors at least $\varepsilon n^2$. As such, \[ \min\{a, b\} > (\varepsilon n^2)^{(n+1) \slash 2} - n > \varepsilon^{n/2} \cdot n^n \]and setting $c \ge \varepsilon$ gives the result.

Posting for storage (in more than one sense) We prove the result for RHS $(cn)^n$ instead. Draw an $N \times N \equiv (n + 1) \times (n + 1)$ grid with a prime dividing $\gcd(a + i, b + j)$ in cell $(i, j)$. notice that for all primes $p$, in any $p \times p$ subgrid, $p$ can only appear once, so picking a suitably small constant $\alpha$, we attempt to determine how many primes at most $\alpha n^2$ can be in the grid: they can only appear in $\sum_{p \leq \alpha n^2} \left \lfloor \frac{N}p \right \rfloor^2$ squares. This is at most $\sum_{p \leq \alpha n^2} \left(\frac{N}p + 1\right)^2 = N^2 \sum_{p \leq \alpha n^2} \frac1{p^2} + 2N\sum_{p \leq \alpha n^2} \frac1p + \sum_{p \leq \alpha n^2} 1$; we'll bound these three sums. by the prime number theorem the third sum is $O\left(\frac{n^2}{\log n}\right)$. the second sum is less than if you sum the reciprocals of every number up to $\pi(\alpha n^2)$ instead, which is $O(\log n)$. for the first sum, notice that $\sum_{n \text{ even}} \frac1{n^2} = \sum_k \frac1{(2k)^2} = \frac14 \cdot \frac{\pi^2}6$, so $\sum_{n \text{ odd}} \frac1{n^2} = \frac{pi^2}6 \cdot \frac34 < \frac54$ since $\pi^2 < 10$. Then $\sum_{p \leq \alpha n^2} \frac1{p^2} < \sum_p \frac1{p^2} < \sum_{n \text{ odd}} \frac1{n^2} - \frac1{1^2} + \frac1{2^2} < \frac12$. Then since the other terms are $o(n^2)$ we can approximate the original sum as being less than $\frac12 n^2$, meaning that at least half of the primes in the grid are at least $\alpha n^2$. So some column or row has half its numbers at least $\alpha n^2$, and if $n$ is large enough then $\alpha n^2 \geq n$ so these primes will only appear once, meaning that the relevant $a + i$ or $b + j$ is at least the product of these primes, which achieves $(cn)^n$ as required. Also, for those coming from QoTD: $\mathcal{C}$ is the largest 3-digit perfect square with a unique tens digit among all such squares, and (4A) is the (lowercase) letter "b". (this is for a scavenger hunt)

It is probably fakesolve, but something like this should work. (I might have messed up in estimating the number of numbers in range [a, a + n] that are not divisible by any of $p_1, p_2, \dots, p_k$) Let $p_k$ be the $k$th prime. Then note that the number of numbers in range $[a, a + n]$ that are not divisible by $p_1, p_2, \dots, p_k$ is approximately $(n+1) \cdot \prod_{i=1}^{k}(1 - \frac{1}{p_i}) > (n+1) \cdot \prod_{i=1}^{p_k}(1 - \frac{1}{i}) = \frac{n+1}{p_k}$. So as long as $p_k < n$, there exists $i$ such that $\gcd(p_1p_2\cdots p_k, a+i) = 1$. Let $s$ be an integer such that $p_s \le n < p_{s+1}$. Then there exists $i$ such that $\gcd(p_1p_2\cdots p_s, a+i) = 1$. Note that $\gcd(a+i, b+j) > 1$ for all $0 \le j \le n$ and $\gcd(\gcd(a+i, b+j), \gcd(a+i, b+k)) = 1$ for all $0 \le j < k \le n$, hence $a+i$ must divisible by at least $n$ distinct primes that are greater than $n$, which means $a+i \ge p_{s+1}p_{s+2}\cdots p_{s+n+1} > n^n$, therefore $a \ge n^n - i \ge n^n - n$. Similarly $b \ge n^n - n$, which is enough to conclude the problem.

First, note that $\sum \frac{1}{p^2} < \frac{\pi^2}{6} - 1 + \frac{1}{4} - \frac{\pi^2}{24} = \frac{\pi^2}{8} - \frac{3}{4}$. Thus we have that $\sum \frac{1}{p^2} < \frac{1}{2}$ is equivalent to $\pi^2 < 10$, which is well known since $\pi^2 \approx g$. Now consider the number of squares of a $n + 1 \times n + 1$ each prime $p$ can cover. This value is at most $\left\lceil \frac{n}{p} \right\rceil^2 <\left(1+\frac{n}{p} \right)^2 \leq \frac{n^2}{p^2} + n+1$. Thus it follows that each prime contributes at most $\frac{1}{p^2} + \frac{1}{n}$ to the sum, and in particular, for $p \geq n$ we must have the contribution is exactly $\frac{1}{n^2}$. Now summing together, since all $(n+1)^2$ squares are covered, we need: $\frac{\pi(n)}{n} + \sum \frac{1}{p^2} + \frac{\textrm{primes at least n present in a gcd}}{n^2}$. Thus by the PNT, the number of primes at least $n$ present in a grid is always at least $\frac{(n+1)^2}{2}$ for sufficiently large $n$. However, since there are only $n+1$ values $a, a+1, \ldots, a_n$, it follows that at least one of them has at least $\frac{n}{2}$ primes at least $n$ dividing it by pigeonhole, so it follows that $a > n^{\frac{n}{2}} - n$ for sufficiently large $n$. In particular, this means we can choose a sufficiently small $c$ to finish the job.

For $0\le i \le n$ and $0 \le j \le n$, let $f(i,j)$ denote the smallest prime that divides both $a + i$ and $b + j$. WLOG that $a \le b$. Claim: For any positive integer $n$, there exists a positive constant $C < \frac 12$ such that the sum of $\frac{1}{p^2}$ over all primes $p \le n$ is less than $C$. Proof: It is well known that $\sum_{i=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}$, so \[\sum \frac{1}{p^2} < \frac{\pi^2}{6} - \sum_{i=1}^{\infty} \frac{1}{(2n)^2 } + \frac{1}{4} - 1 = \frac{\pi^2}{8} - \frac 34\]since $1$ isn't prime and $2$ is the only even prime. It remains to show that this is less than $\frac 12$, which is evident as $\pi^2 <10$. $\square$ Claim: For sufficiently large $n$, more than half of the $(n+1)^2$ possible integer pairs $(i,j)$ with $0 \le i,j \le n$ satisfy $f(i,j) > n$. Proof: Consider some prime $p$. Among the $n+1$ values $a, a+1, \ldots, a + n$, at most $\frac np + 1$ of them are multiples of $p$. This is also true among the values $b, b+1, \ldots, b + n$. Hence the number of $(i,j)$ with $f(i,j) = p$ is at most \[\left( \frac np + 1 \right)^2 = \frac{n^2}{p^2} + 2 \cdot \frac{n}{p} + 1 \le \frac{n^2}{p^2} + n + 1 \]Summing this over all primes $p \le n$, we see that there are at most \[ n^2 \sum \frac{1}{p^2} +(n+1) \pi(n) < C \cdot (n+1)^2 + (n+1)\pi(n) \]$(i,j)$ with $f(i,j) \le n$, where the sum is taken over all primes at most $n$. Note that $\frac{n}{\pi(n)}$ approaches $\ln(n)$ and is thus unbounded. Since $n$ is sufficiently large, we can choose $n$ large enough so that $\frac{n+1}{\pi(n) } > \frac{n}{\pi(n)} > \frac{1}{\frac{1}{2} - C} $. Hence $(n+1) \pi(n) < (n+1)^2 \left( \frac 12 - C \right)$, so there are less than \[(n+1)^2 \left( C + \frac 12 - C \right) = \frac{(n+1)^2}{2}\]$(i,j)$ with $f(i,j) \le n$, implying the claim. $\square$ Now for any sufficiently large $n$, by Pigeonhole, there must exist some integer $0\le k\le n$ such that more than half of the pairs $(k,j)$ with $0\le j \le n$ satisfy $f(k,j) > n$. Since no prime greater than $n$ can appear in $f$ twice, $a + k$ has more than $\frac{n+1}{2}$ distinct prime divisors greater than $n$, implying that \[a \ge (a+k) - n \ge n^{ \frac{n+1}{2} } - n > n^{ \frac{n}{2}} \]Since $a \le b$, we have $\min(a,b) > n^{\frac{n}{2}}$, so $c = 1$ satisfies the problem condition for all sufficiently large $n$. For the other (finitely many) $n$, we can just decrease the constant $c$ so that also satisfy the inequality.

It suffices to show that this is true for arbitrarily large $n$ as we can manually reduce $c$ to deal with the finite cases. Denote $N$ as $n+1$ for sufficiently large $n$ and consider a grid with rows and columns labeled $a + i$ and $b + i$ respectively with the bijection to the problem being obvious. WLOG that the number of rows is less than or equal to the number of columns. Let $K = \epsilon n^2$ with $\epsilon$ being some small positive number less than $1$ and choose. Then consider the set of primes $p < K$. Notice that the number of cells that a prime $p$ divides in the grid is at most $\left(\left\lceil \frac{N}{p} \right\rceil\right)^2$, so the total amount of numbers that the set of primes less than $K$ covers is \[\sum_{p \leq K} \left(\left\lceil \frac{N}{p} \right\rceil\right)^2 \leq \sum_{p \leq K} \left(\frac{N}{p} + 1\right)^2 = \sum_{p \leq K} \frac{N^2}{p^2} + \frac{2N}{p} + 1\]It is well known that $\sum_{p > 1} \frac{1}{p^2} < \frac 12$, so \[\sum_{p \leq K} \frac{N^2}{p^2} + \frac{2N}{p} + 1 < \frac{N^2}{2 + d} + O(K\log\log K) + O(K)\]for some small number $d$. Then the other terms are negligible so we get that the number of cells that the primes less than $M$ cover are less than half of the grid for sufficiently large $N$. By Pigeonhole, this implies that there is a row of the grid $a+i$ so that there are $\frac{n}{2}$ primes $p_i \geq \epsilon n^2$. Since all of these primes divide $a + i$, we have \[a \geq \prod_{i} p_i - i \geq \epsilon^{\frac{n}{2}}n^n - i\]we can reduce $\epsilon$ by a sufficient amount to get $c$ so that $c^{\frac{n}{2}}n^n \leq \epsilon^{\frac{n}{2}}n^n - i$ which is a valid constant $c$ so we are done.