The probability that Caitlin fought the dragon

For discussing Olympiad Level Combinatorics problems
User avatar
Enthurelxyz
Posts:17
Joined:Sat Dec 05, 2020 10:45 pm
Location:Bangladesh
Contact:
The probability that Caitlin fought the dragon

Unread post by Enthurelxyz » Wed Mar 31, 2021 11:17 am

Caitlin is playing an game on a $3*3$ board. She starts her marker in the upper-lest square, and each turn she randomly chooses an adjacent square to move her marker to.(She can’t move diagonally.) If she moves to the center square, she fights the dragon.

After Caitlin has moved her marker four times, what is the probability that she has fought the dragon exactly once?

Let do a thing: you'll try this problem for 20 minutes. If you can solve the problem then give the solution. If you can't, you can write how you have approached the problem for 20 minutes

This is how I have approached.
Let every unit square is a node and the path is edge. Then I had tried to figure out that how many paths we can create by 4 edges and how many of them go through the middle node. I tried some experiments but I can't figure this out.
and miles to go before we sleep
and miles to go before we sleep

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: The probability that Caitlin fought the dragon

Unread post by Mehrab4226 » Wed Mar 31, 2021 2:04 pm

I used $12$ minutes to find this. There may be mistakes so sorry ;)
Observation:
It is clear that we can get to the centre only from an edge. We can not get to the centre from a corner. Let's say we are not allowed to go into the centre square. Then in which move we can go to an edge or corner? It is clear we can go to the edge by only an odd number of moves regardless of whether we go into the centre or not. So we can reach the corner squares by only an even number of moves. So we can get to the middle square by only even number of moves. This divides our solution into $2$ cases, when Caitlin reaches the middle square at the $2nd$ or $4th$ move.
Solution:
Let us denote the $3\times 3$ square grid by numbers. It will help us to explain things better. Just like in the picture;
Grid.png
Grid.png (6.57KiB)Viewed 4912 times
So we need start from $1$ and we need to reach $5$.
Case1:
We reach $5$ in the $2nd$ move.
We can reach $5$ by only $2$ ways,
  • $1\to 2\to 5$
    $1\to 4\to 5$
We still have $2$ moves left.
From $5$ we can go to $4$ other edges. And from those $4$ edges, we can go to the $2$ other corners. (Note that we can't go back to $5$ as we can only enter $5$ once).
So total ways Caitlin can do $4$ moves and get into $5$ in the $2nd$ move is $2\times4\times2=16$

Case:2
Getting into $5$ in the $4th$ move.
This is the same as saying how many ways we can reach an edge using $3$ moves. Actually, with $3$ moves, we will always reach an edge. But we need to avoid using the centre. Let us see how Caitlin can reach the square $6$. There is only one way, $1\to 2\to 3 \to 6$
Now how can Caitlin reach $2$ in $3$ moves?
There are actually $3$ ways
  • $1\to 2\to3\to2$
    $1\to 2\to 1\to 2$
    $1\to 4\to1\to 2$

So we can reach either $2$ or $6$ in $4$ ways. Similarly, we can move to $4,8$ in $4$ ways. So we can reach an edge in $3$ moves in $8$ ways. The last move is fixed which is to go to $5$.
So total number of favourable outcome $=16+8=24$

Now to find the total number of outcomes.
$2$ cases,
Case:1
We go in $5$ in the $2nd$ move,
Then the number of $4$ moves is $=2\times 1\times 4\times 3=24$
Case:2
We do not go in $5$ in the $2nd$ move,
Then the number of $4$ moves is $=2\times 2\times 2\times 3=24$
So total number of moves $=48$
So probability $=\frac{24}{48}=\frac{1}{2}$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: The probability that Caitlin fought the dragon

Unread post by Asif Hossain » Thu Apr 01, 2021 12:15 pm

Enthurelxyz wrote:
Wed Mar 31, 2021 11:17 am


Let do a thing: you'll try this problem for 20 minutes. If you can solve the problem then give the solution. If you can't, you can write how you have approached the problem for 20 minutes
off topic :
hmmm i see you are very competitve :roll:
Hmm..Hammer...Treat everything as nail

User avatar
Enthurelxyz
Posts:17
Joined:Sat Dec 05, 2020 10:45 pm
Location:Bangladesh
Contact:

Re: The probability that Caitlin fought the dragon

Unread post by Enthurelxyz » Thu Apr 01, 2021 12:53 pm

Asif Hossain wrote:
Thu Apr 01, 2021 12:15 pm
Enthurelxyz wrote:
Wed Mar 31, 2021 11:17 am


Let do a thing: you'll try this problem for 20 minutes. If you can solve the problem then give the solution. If you can't, you can write how you have approached the problem for 20 minutes
off topic :
hmmm i see you are very competitve :roll:
Is it bad? :(
and miles to go before we sleep
and miles to go before we sleep

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: The probability that Caitlin fought the dragon

Unread post by Asif Hossain » Thu Apr 01, 2021 12:56 pm

Enthurelxyz wrote:
Thu Apr 01, 2021 12:53 pm
Asif Hossain wrote:
Thu Apr 01, 2021 12:15 pm
Enthurelxyz wrote:
Wed Mar 31, 2021 11:17 am


Let do a thing: you'll try this problem for 20 minutes. If you can solve the problem then give the solution. If you can't, you can write how you have approached the problem for 20 minutes
off topic :
hmmm i see you are very competitve :roll:
Is it bad? :(
:mrgreen: bad for noobs like me we get depressed by such statement :( :(
Hmm..Hammer...Treat everything as nail

Post Reply