Wait wasn't it the reciprocal in the paper?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Wait wasn't it the reciprocal in the paper?

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India TST 2023 Day 2 P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1260 posts

#1 h Jul 9, 2023, 6:31 PM • 1 Y

Y by MS_asdfgzxcvb

Let $\mathbb{Z}_{\ge 0}$ be the set of non-negative integers and $\mathbb{R}^+$ be the set of positive real numbers. Let $f: \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}^+$ be a function such that $f(0, k) = 2^k$ and $f(k, 0) = 1$ for all integers $k \ge 0$ , and $f(m, n) = \frac{2f(m-1, n) \cdot f(m, n-1)}{f(m-1, n)+f(m, n-1)}$ for all integers $m, n \ge 1$ . Prove that $f(99, 99)<1.99$ .

Proposed by Navilarekallu Tejaswi

This post has been edited 4 times. Last edited by Supercali, Jul 11, 2023, 12:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

339 posts

#3 h Jul 11, 2023, 4:33 AM

Y by

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).

This post has been edited 1 time. Last edited by AnonymousBunny, Jul 11, 2023, 11:57 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

100 posts

#4 h Jul 13, 2023, 3:59 AM

Y by

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.

This post has been edited 1 time. Last edited by falcon311, Jul 13, 2023, 4:00 AM
Reason: missed some info

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

904 posts

#5 h Nov 22, 2023, 5:44 PM • 2 Y

Y by Ankoganit, MS_asdfgzxcvb

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}$ .

This post has been edited 2 times. Last edited by Rijul saini, Nov 23, 2023, 4:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1979 posts

#6 h Nov 23, 2023, 4:42 AM • 4 Y

Y by starchan, math_comb01, everythingpi3141592, MS_asdfgzxcvb

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#7 h Apr 24, 2024, 11:15 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11 posts

#8 h Mar 15, 2025, 8:06 AM

Y by

AnonymousBunny wrote:

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).

I think the reflection argument shows $A=C$ , not $B=C$ .
Furthermore, for computing $A/B$ , my calculation gave $(A+B)/C = (k+2)/k$ . Hence $A:B:C = k : 2 : k$ , and the probability is $\frac{k+2}{2k+2} \geq \frac{1}{2} + \frac{1}{2n+1}$ , which is weaker than $\frac{1}{2} + \frac{1}{2n-1}$ you claimed but still suffices because that value is $\frac{100}{199} = 1.99^{-1}$ . If you have spare time please calculate again and edit post or reply to check out who is right

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11 posts

#9 h Mar 15, 2025, 11:23 AM

Y by

Surprised that everyone's solution uses relatively hard concepts like random walk or generating functions.
Actually it is straight forward induction (on $m+n$ ) that
$\frac{1}{f(m,n)} =\frac{1}{2^{m+n}}\sum_{i=0}^n\binom{m+n}{i}$ (it holds for $m=0$ or $n=0$ by definition, and assuming true for $m+n-1$ the inductive step follows from $\sum_{i=0}^{n-1}\binom{m+n-1}{i}+\sum_{i=0}^n\binom{m+n-1}{i}=\sum_{i=0}^n\binom{m+n}{i}$ .)
Now using the fact that $\binom{198}{99}$ is maximum among $\binom{198}{r}$ ,
$\frac{1}{f(99,99)}=\frac{1}{2^{198}}\sum_{i=0}^{99}\binom{198}{i}=\frac{1}{2}(1+\frac{1}{2^{198}}\binom{198}{99})>\frac{1}{2}(1+\frac{1}{199})=\frac{100}{199}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a