An insect is situated on the vertex of a regular tetrahedron. It can move to any of the three vertex in each move and can retrace its path. In how many ways can the insect move such that after 6 steps it is back to its starting position?
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.
The problem can be interpreted as follows:
To find the number of strings of length 7 that can be made from the letters A , B , C , D such that the first and the last letters are both A and there are no two consecutive letters in any position.
We can solve this by considering cases on the first time the letter A occurs after the first place.Then we get the recurrence ,
f ( 6 ) = 3 × f ( 4 ) + 3 × 2 f ( 3 ) + 3 × 2 2 f ( 2 ) + 3 × 2 4
It is simple to see that f ( 2 ) = 3 , f ( 3 ) = 6 and f ( 4 ) = 2 1 .
We then get f ( 6 ) = 1 8 3