Anna's quest
After her long journey, Anna finally arrives at an ice kingdom.
There are five rooms adjacent to one another. Anna stands dumbfounded, only knowing that Elsa is in one of these rooms. She then enters the middle door.
Elsa upon knowing this, fled from the room, using her ice powers, she teleports from room to room.
Upon realizing that the room was empty, Anna enters a door leading to an adjacent room. Given that she passed through 13 doors in total before she found Elsa, how many possible paths could she have taken?
Note: She starts from the middle door. You can only go to adjacent rooms. The door to enter the middle room at the beginning is not counted.
The answer is 1458.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
For this, i used a Markov chain type of idea. Let (a,b,c,d,e) denote the number of ways Anna can get into each door, so for example (1,0,2,0,1) would denote that at a certain stage, Anna could have gotten to the middle door 2 ways and the left and right most doors 1 way each. And let P(x) denote this specific instance after x door openings. So, for example, P(0)=(0,0,1,0,0).
Further more, notice that for any given a in P(a)=(a1,a2,a3,a4,a5), P(a+1)=(a2,a1+a3,a2+a4,a3+a5,a4). Basically, to get from P(a) to P(a+1) you take each door, and add the adjacent two doors numbers to get that doors new number.
So therefore,
P(0)=(0,0,1,0,0)
P(1)=(0,1,0,1,0)
P(2)=(1,0,2,0,1)
P(3)=(0,3,0,3,0)
P(4)=(3,0,6,0,3)
… The thing to notice is that if we look at any P(b) where b is odd, P(b)=3xP(b-2). To prove this, consider P(b-2)=(0,n,0,n,0). Thus, P(b-1)=(n,0,2n,0,n) and P(b)=(0,3n,0,3n,0). Thus, if P(b-2) has the first, middle, and last door impossible to get to, so does P(b), and therefore so does P(b+2), and therefore P(b+4), etc, etc, and that all of these follow the pattern of tripling each time. Since P(1) follows this condition, so must all P(L) where L is any given odd number.
Since P(13)=P(1+12), we know that P(13) = 3^(12/2)xP(1). Thus, P(13)=(0,729,0,729,0) and therefore the total number of paths Anna could have taken are 0+729+0+729+0=1458.