Lily pads numbered from 1 to 2022 are placed on a pond. Bruno the frog starts on pad 1. Every moment

[sharp heart]

Aight so

[fathom vapor]

yes

[sharp heart]

I think we try doing it for like say we are at a pad y then the probability of going to pad z in on Jump is (where z >y) is 1/2022-y

Now we want to go to 2000 so our second last jump must be from any x less than 2000 right?

[fathom vapor]

ye

[fathom vapor]

and it is currently at pad one
so the maximum number of jumps it can make in order to reach pad 2000 is 1999

since it is already at 1

[sharp heart]

So ig p(2000)= $\sum_{i=1}^{1999} \frac{1}{2000-i} *p(i)$

[polar wharf]

icebear

[sharp heart]

Right?

[fathom vapor]

so, 1/1999*p(1999)

since i is 1

and then it goes upto 1999

[sharp heart]

So we replacing 2000 with n we have the recurrence relationship p(n)= $\sum_{i=1}^{n-1} \frac{1}{n-i} *p(i)$

[polar wharf]

icebear

[fathom vapor]

and add all of the values

[sharp heart]

I donot understand what you are trying to say

[fathom vapor]

aight, can u try solving it and tell me the final probability please

[sharp heart]

Hmm lemme see

[fathom vapor]

summation of the different values of 1/2000-i
where i takes values from 1 to 1999
and then multiple that with p(i) where i goes from 1 to 1999

the same thing

well anyways

[fathom vapor]

yes, thanks a lot for ur help bud

[sharp heart]

I have made a mistake here it should be $$p(n)=\sum_{i=n}^{n-1} \frac{1}{2022-i} *p(i)$$

[polar wharf]

icebear

[sharp heart]

Now note $$p(n+1)=\sum_{i=1}^{n} \frac{1}{2022-i} *p(i)$$ $$=\frac{1}{2022-n} *p(n) + \sum_{i=1}^{n-1} \frac{1}{2022-i} * p(i)$$ $$p(n+1)= \frac{p(n)}{2022-n} + p(n-1)$$

[fathom vapor]

okay

alr

[polar wharf]

icebear

[sharp heart]

This should be easier to solve I think 💀

Also let me know if you spot any mistakes till now

[fathom vapor]

honestly it is not. It going way above my head

my apologies to disturb a lot

but can you try and solve it completely and give me the final answer

[fathom vapor]

well, as far as i can understand, I don't think there are any errors

[sharp heart]

Simplifying this we get (2022-n)p(n+1)= p(n) + (2022-n)*p(n-1)
Implies p(n+1)-p(n-1)= p(n)/(2022-n)
Now I think we can use the method of generating functions

Get F(x) = \sum p(t) x^t

So consider x^2F(x)-F(x)

So we have (x^2-1)F(x)= 1+ \sum x^n (p(n+2)-p(n))

= \sum x^n p(n)/2022-n

= -sum x^n p(n) /n-2022

=-(x^2021* integral of F(x))

So now we have a differential equation

💀

Wait I messed up somewhere for sure 💀

[fathom vapor]

where?
u sure lmao

[sharp heart]

This seems needlessly complicated there must be a fault with my methods

[fathom vapor]

well yea. It did go complicated yes 💀

but i don't think the procedure is wrong though

[sharp heart]

Same but I think uptil the recurrence it was right

Also the nature is additive

[fathom vapor]

hmm

yes

so, are you going to try a different approach

or 😂

do we consider it closed

[sharp heart]

@fathom vapor is it supposed to have "simpler" solution

Like elementary?

Cause this is involving some higher math

And I don't see any faults with my approach (although i may be stupid)

[fathom vapor]

I do not think so
besides, I came upto the recurrence relation in my own solving as well and after that it went all South

[fathom vapor]

nope, no way

it does involve higher level math

[sharp heart]

Oh okay

[fathom vapor]

that is brilliant

then go ahead and well let's see what answer does that give you

[sharp heart]

So uh you obtained the same recurrence as p(n+1)=p(n)/2022-n + p(n-1)?

[fathom vapor]

yes

or maybe i step before that

[fathom vapor]

I went till here

and then began looking for help

😂

[sharp heart]

Yeah the way it turned out with the gen function approach I would do the same

[digital oxide]

i think i found a nice way to solve it

[fathom vapor]

but ur approach seems accurate, so try to follow the steps and see what final answer does that give you ig

[digital oxide]

think of the same situation but there are only 5 lilypads in total

(including the first one)

im going to type some binary numbers

how its going to work is if the third digit is a one, that means the frog landed on the third lilypad

im going to ignore the first digit because it's always 1

[fathom vapor]

also @sharp heart try out ur way and lmk where does that take u

[fathom vapor]

okay alr

[digital oxide]

here are all possible scenarios for 5 lilypads: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

now we don't consider all numbers that end in 0 because the frog has to end on lilypad 5

[sharp heart]

@fathom vapor I see my error here
$$\sum_{i=1}^{n-1}$$ is not p(n-1) it's p(n) cause we defined it like that

💀

[polar wharf]

icebear

[sharp heart]

So the recurrence is p(n+1)= p(n) (1/2022-n +1)

P(n+1)= p(n)(2023-n/2022-n)

Now it's a telescoping product I think

@fathom vapor

[fathom vapor]

ohh rightt yes. The initial variables were defined in that way

[fathom vapor]

hmm

alr

[sharp heart]

This should be doable

[fathom vapor]

try it out sir 🙏

[sharp heart]

Okay 😭💀

[fathom vapor]

thnx mate

[fathom vapor]

okay, how are you going to solve it for 2022 lilypads?

[digital oxide]

in binary the number 1111 is equal to 15 or 2^4-1

11111 is equal to 31 a.k.a. 2^5-1

[digital oxide]

notice that all i was doing here was counting all the binary numbers from 0000 to 1111

so we know there are 16 possibilites

half of which end in 0, we dont consider those because the frog must land on the last pad

That leaves us with 8 real possibilities

Say we wanted to find the probability that the frog lands on pad 3 at some point

Each number that has a 1 as the third digit is a time that he lands on the third lily pad

Half of our numbers have a 1 as the third digit meaning the probability is 4/8

I explained that really and

Badly

but it's not too hard to see that there are $2^{n-1}$ possibilities and $2^{n-2}$ of which where the frog lands on say, the 1000th lilypad, where n is the number of lilypads

[polar wharf]

Daniel_The_Maniel

[sharp heart]

Daniel

I think you need to consider that he can't go back

To a smaller number

[digital oxide]

i dont think so

[fathom vapor]

but the frog can not go backwards

[sharp heart]

And it changes dynamically with his position

[digital oxide]

tell me which one of my numbers here represents a time when he goes backwards

say you have 1011

[fathom vapor]

it only goes forward and the maximum number of steps it can take to reach the 2000th lily pad is 2000 itself

[digital oxide]

thats true

but its irrelevant

im not saying that the he can take 2^2022 steps

im saying thats how many possibilites there are in total

maybe i overlooked something idk

[sharp heart]

@fathom vapor
We obtained
$$p(n+1)= \frac{2023-n}{2022-n} p(n)$$
So for 2000 we obtain
$$ p(2000)= \frac{1}{2022-1999} p(2)(2023-2)$$
P(2)=1/2021
So we get
P(2000)= $\frac{2021}{23*2021}$

[polar wharf]

icebear

[sharp heart]

Which is 1/23

Let me know if there are any errors

[fathom vapor]

but i don't think the total number of possibilities also exceeds 2022 because the total number of lilypads again is 2022 and the frog does not go backwards

[sharp heart]

I am not using pen paper so it's hard to keep track of

[fathom vapor]

yes, that looks correct

[fathom vapor]

I shall verify and get back to you sir

thanks a lot for your help

[sharp heart]

@fathom vapor where is this problem from btw

[fathom vapor]

both of you

[digital oxide]

np

[fathom vapor]

really appreciate it

[digital oxide]

im probably wrong tho

but i got 1/2

[fathom vapor]

it's from an examination in the Indian Institute of Science

[sharp heart]

No way 💀

[fathom vapor]

yes lol

why tho

what happened?

[sharp heart]

Nothing

I thought that this was some amc problem

And was supposedly looking for simple solutions

[fathom vapor]

the effort matters. Thank you for your time and effort mate

[fathom vapor]

lmfao

[fathom vapor]

it was complicated yes. In fact, very much so tbh

[digital oxide]

hold on am i misunderstanding the quesiton

[sharp heart]

It got much more complicated because I messed upmy recurrence 💀

[digital oxide]

the way i understand is that it's asking whether or not the frog lands on lilypad #2000 at some point in time during his journey

[sharp heart]

Yes it is

[fathom vapor]

ye lol, but the current answer looks right. So all cool hahayes

[sharp heart]

But that journey is restricted

[digital oxide]

ok just making sure

wait im pretty sure im right

the chance of him landing on lilypad #2000 is the same as the chance of him not landing on lilypad #2000

2 possibilities with equal probability, so its 50/50

like a coin flip

am i missing something?

[sharp heart]

What if say Daniel it was lily pad number 3

In the given setting

What do u think the probability would be

[digital oxide]

1/2

[sharp heart]

So every landing has same probability?

[digital oxide]

the probability of him landing on any given lilypad at some point in his journey would be 1/2 so yes

[sharp heart]

Well let's say he is at 1 and he wants to go to 2

Then isn't there a condition of the problem that says

He picks a number greater than the 1 he's on uniformly

So from 1 he wants to go to 2
There are 2021 numbers greater than 1 in this setting

And the probability of going to each number is same

So shouldn't it be 1/2021

Which is not half?

[digital oxide]

this is the probability he lands on any given lilypad out of all 2021 lilypads in front of him in that one leap

say we were trying to find the probability he lands on 2000th one

[sharp heart]

Yeah we are supposed to find this probability for 2000 th lilypad land

Given he's on one

[sharp heart]

He will land on any lilypad with certainty but I want it to land on that one special lilypad

So it's 1/2021

[digital oxide]

we'd have to consider all cases where he lands on lilypad 2022, some examples: 1->2->2000->2022 or 1->1000->2000->2010->2022

not just the case where he goes 1->2000->2022

[sharp heart]

Yes

That's why we use the recurrence

[fathom vapor]

yes

1/23 is the right answer

[fathom vapor]

exactly what even i thought and considered the recurrence relations

there are multiple ways he could go to lily pad number 2000

[digital oxide]

oh yeah theres no way its 1/2

[fathom vapor]

it could be a direct jump from 1 to 2000
or it could be in 2 jumps 1-> 1000 -> 2000
or even a 1002 jumps 1->100->101->102....1000->2000

[fathom vapor]

yes. It's fine though lmao

[digital oxide]

I made the assumption that all journeys had an equal probability of occuring