Let $g(m,n)=1/f(m,n)$. Consider a random walk starting from $(m+1,n)$ where at each step we go left or down 1 unit with equal probability. Then, $g(m,n)$ is the probability that we touch the line $y=0$ before we touch the line $x=0$. So we want to estimate the following quantity: start a random walk from $(n+1,n)$. What is the probability we hit $y=0$ before $x=0$? Let $E$ denote this event. Let $P_i=(x_i,y_i)$ be the $i$th point in the step and let $v$ be the largest $i$ such that $|y_i-x_i|=1$. Condition on $v=k$; we want to estimate $P(x_k>y_k|v=k)$. I claim this is $\geq 1/2+1/(2n-1)$ Consider a set of lattice paths where from each $(x,y)$ we go to either $(x+1,y+1)$ or $(x+1,y-1)$. Let $A$ be the number of such length $k$ paths from $(0,1)$ to (k,1) which touch the line $y=0$, $B$ be the number of paths from $(0,1)$ to $(k,1)$ which don't touch the line $y=0$ and let $C$ be the number of paths from $(0,1)$ to $(k,-1)$. By standard bijection arguments, the conditional probability we want to compute is $(A+B)/(A+B+C)$. Moreover, by reflection argument, $B=C$, and by using Catalan numbers, $A=(A+B/((k-1)/2)$. Since $k \leq 2n$, we get that $A/(B+C) \geq 1/2+ 1/(2n-1)$. Now simply note that $E$ is true iff $x_v>y_v$ where $v$ is defined as above. Since for each conditioning of $v$ the conditional probability is $\geq 1/2+ 1/(2n-1)$ we get that $g(n,n) \geq 1/2+ 1/(2n-1)$. In fact this inequality must be strict because the conditional probability is strictly larger for small values of $v$ (which have a nonzero probability).

in the real test it was typod so $2^k$ became $\frac{1}{2^k}$ The typo made it super easy... Everyone except for 1 person solved it.

Let $g(m,n) = \frac{1}{f(m,n)}$. Then $g(0,k) = \frac{1}{2^k}$, $g(k,0) = 1$ for all integers $k \ge 0$, and $$2 \cdot g(m,n) = g(m-1,n) + g(m, n-1)$$for all integers $m,n \ge 1$. Let $G(x,y) = \sum_{m,n \ge 0} g(m,n) x^m y^n$ be the generating function of $g(m,n)$. Claim 1: $\color{blue}{G(x,y) = \frac{1}{(2-x-y)} + \frac{1}{(1-x)(2-x-y)}}$ Proof: Multiplying both sides of $2 \cdot g(m,n) = g(m-1,n) + g(m, n-1)$ by $x^my^n$ and summing over all $m,n \ge 1$, we get \begin{align*} \sum_{m,n \ge 1} 2 \cdot g(m,n) x^m y^n &= \sum_{m,n \ge 1} g(m-1,n) x^m y^n + \sum_{m,n \ge 1} g(m, n-1)x^m y^n \\ 2 \left(G - \frac{1}{1-x} - \frac{2}{2-y} + 1 \right) &= x \left(G - \frac{1}{1-x} \right) + y \left(G - \frac{2}{2-y} \right)\\ (2-x-y)G &= \frac{2-x}{1-x} = 1 + \frac{1}{1-x}\\ G(x,y) &= \frac{1}{(2-x-y)} + \frac{1}{(1-x)(2-x-y)} \end{align*} Claim 2: $\color{blue}{g(m,n) = \frac{1}{2^{m+n+1}} \binom{m+n}{n} + \sum_{k =0}^{m} \binom{n+k}{n} \frac{1}{2^{n+k+1}} }$. Proof: Taking coefficient of $x^my^n$ in the generating function from Claim 1. Claim 3: $\color{blue}{\sum_{k=0}^{n} \binom{n+k}{n} \frac{1}{2^{n+k+1}} = \frac 12}$. Proof: This seems fairly well known. There are three proofs I know of this. The easiest is to simply prove it by induction on $n$. The second to consider the situation of flipping a fair coin repeatedly until having $n+1$ heads, and then seeing if the $(n+1)^{th}$ head appears before the $(n+1)^{th}$ tail. For fun, here's a third solution using generating functions: \begin{align*} \sum_{k=0}^{n} \binom{n+k}{n} \frac{1}{2^k} &= \sum_{k=0}^{n} [x^k] \left(1+\frac{x}{2} \right)^{n+k} \\ &=\sum_{k=0}^{n} [x^n] x^{n-k}\left(1+\frac x2 \right)^{n+k} \stackrel{k \mapsto n-k}{=} [x^n] \sum_{k=0}^n x^k \left(1+ \frac x2 \right)^{2n-k} \\ & = [x^n] \left(1+ \frac x2 \right)^{2n} \frac{1 - \left(\frac{x}{1+ \frac x2} \right)^{n+1} }{1 - \left(\frac{x}{1+ \frac x2} \right)} \\ & = [x^n] \left(1+ \frac x2 \right)^{n} \frac{\left(1+\frac x2 \right)^{n+1} - x^{n+1}}{1 - \frac x2} \\ & = [x^n] \frac{\left(1+\frac x2 \right)^{2n+1}}{1 - \frac x2} - \underbrace{[x^n] x^{n+1} \cdot \left(1+ \frac x2 \right)^{n} \frac{1}{1 - \frac x2} }_{=0} \\ & \stackrel{y = \frac x2}{=} \frac{1}{2^n} [y^n] \frac{(1+y)^{2n+1}}{1-y} \\ & =\frac{1}{2^n} \sum_{k=0}^{n} \binom{2n+1}{k} = \frac{1}{2^n} \cdot 2^{2n} = \boxed{2^n}. \end{align*} Claim 4: $\color{blue}{g(n,n) > \frac{1}{2 - \frac{1}{n+1}} }$, and therefore $\color{blue}{g(99,99) > \frac{1}{1.99} }$. Proof: By Claim 2, $g(n,n) = \frac{1}{2^{2n+1}} \binom{2n}{n} + \sum_{k =0}^{n} \binom{n+k}{n} \frac{1}{2^{n+k+1}} = \frac{1}{2^{2n+1}} \binom{2n}{n} + \frac 12$, where the last equality is by Claim 3. Now, $\frac{1}{2 - \frac{1}{n+1} } = \frac{n+1}{2n+1} = \frac 12 + \frac{1}{2(2n+1)}.$ Thus, it suffices to observe that $\binom{2n}{n} > \frac{1}{2n+1} \cdot 2^{2n}$, which is true because it is the largest number among the $(2n+1)$ numbers $\binom{2n}{k}$ for $0 \le k \le 2n$ and their sum is $2^{2n}$.

The solution that follows uses a pretty fun main idea: instead of computing the recursion by going down all the way to the $x$ or $y$ axes, we instead go down all the way to the line $y=-x$ which has binary values, and simply compute the number of paths going to each point there. I have not seen this trick used elsewhere, but it felt really cool Define $a_{m, n}=\frac{1}{f(m, n)}$ for all $m, n \ge 0$, this is well-defined as $f$ takes only positive values. Then $a_{0, k}=2^{-k}$ and $a_{k, 0}=1$ for all $k \ge 0$, and $a_{m, n}=\frac{1}{2}(a_{m, n-1}+a_{m-1, n})$ for all $m, n \ge 1$. Extending $a_{m, n}=\frac{1}{2}(a_{m, n-1}+a_{m-1, n})$ gives $a_{1, -1}=1, a_{2, -1}=1, \dots, a_{k, -1}=1$ for all $k \ge 1$. Extending downwards in similar fashion, $a_{m, n}=1$ for all $m>0, n<0$ with $m+n \ge 0$. Similarly, since $\frac{1}{2^{k+1}}=\frac{1}{2}\left(\frac{1}{2^k}+0\right)$, we conclude that $a_{m, n}=0$ for all $m<0, n>0$ with $m+n<0$. Thus, the diagonal element $a_{k, -k}$ is $0$ if $k<0$ and $1$ if $k \ge 0$. Consider now the computation for $a_{n, n}$: expanding the recursion till we reach the diagonal line $y=-x$, gives it as a linear combination of the diagonal elements. The weight of each $a_{x, -x}$ is given by adding $\frac{1}{2^{\text{path length}}}$ over all paths from $(n, n)$ to $(x, -x)$ that go either down or left in each step. The length of all such paths if $(n-x)+(n-(-x))=2n$, and the number of such paths is $\binom{2n}{n+x}$. Thus, $$a_{n, n}=\frac{1}{2^{2n}} \cdot \left(\sum_{k=0}^{2n} a_{k-n, n-k} \cdot \binom{2n}{k}\right)=\frac{1}{2^{2n}} \cdot \left(\sum_{k=n}^{2n} \binom{2n}{k} \right)=\frac{1}{2^{2n}} \left(\frac{1}{2}\left(2^{2n}+\binom{2n}{n}\right)\right).$$ By the well-known fact that $\binom{2n}{n} \ge \binom{2n}{k}$ for any $k$, and $2^{2n}=\sum_{r=0}^{2n} \binom{2n}{k} < (2n+1)\binom{2n}{n}$ for $n>1$, we get that $a_{n, n} > \frac{1}{2}\left(1+\frac{1}{2n+1}\right)=\frac{n+1}{2n+1}$, so $f(n, n) < 2-\frac{1}{n+1}$ for all $n>1$. So, $f(99, 99) < 1.99$.

Let $g(n)=\frac1{f(n)}$ for every $n$. Then, we have \[g(m,n)=\frac{g(m-1,n)+g(m,n-1)}2\]and $g(0,k)=\frac1{2^k}$, $g(k,0)=1$. We need to show that $g(n,n)>\frac{n+1}{2n+1}$ for every $n$. Here's a standard solution of the same, using generating functions. (We explicitly find $g(n,n)$ in terms of $n$.) Let $G(x,y)=\sum_{m,n\geq0}g(m,n)x^my^n$ Then, we have that $G(x,y)-\left(\frac{x+y}2\right)G(x,y)=\frac12+\frac1{2(1-x)}$ as most terms just cancel and we're left with geometric series. So, we get $G(x,y)=\frac1{2-x-y}+\frac1{(2-x-y)(1-x)}$ Now, coefficient of $x^my^n$ in $G(x,y)$ is $\frac1{2^{m+n+1}}\binom{m+n}{n}+\frac1{2^{m+n+1}}\sum_{t=0}^{m}2^{m-t}\binom{n+t}{n}$. So, we have \[g(n,n)=\frac1{2^{2n+1}}\binom{2n}n+\frac1{2^{2n+1}}\sum_{t=0}^{n}2^{n-t}\binom{n+t}n\]It is well-known that $\sum_{t=0}^{n}\frac1{2^{n+t+1}}\binom{n+t}n$ is actually just $\frac12$. Here's a proof using generating functions: Let $H(x)=\sum_{t=0}^{n}x^{n-t}\left(1+\frac x2\right)^{n+t}$ We just want the coefficient of $x^n$ from this and to show it is $2^n$. Note that $H(x)=\sum_{t=0}^{n}x^t\left(1+\frac x2\right)^{2n-t}=\left(1+\frac x2\right)^{2n}\left(\frac{1-\left(\frac{x}{1+\frac x2}\right)^{n+1}}{1-\left(\frac{x}{1+\frac x2}\right)}\right)=\left(1+\frac x2\right)^n\frac{\left(1+\frac x2\right)^{n+1}-x^{n+1}}{1-\frac x2}$ and, as usual, ignore the large powers. So, it is same as finding coefficient of $x^n$ from $\left(1+\frac x2\right)^{2n+1}\left(1+\frac x2+\left(\frac x2\right)^2+\cdots\right)$, but that is simply $\sum_{i=0}^{n}\binom{2n+1}i2^{-n}=2^n$, as required. So, we have $g(n,n)=\frac12+\frac1{2^{2n+1}}\binom{2n}n$. We had to show that $g(n,n)>\frac{n+1}{2n+1}$. It suffices to show that $\binom{2n}n>\frac{2^{2n}}{2n+1}$. But that is true, because $\binom{2n}n>\binom{2n}{n-1}>\cdots>\binom{2n}0$ and the sum of these numbers is more than $2^{2n}$. We're done. $\blacksquare$