document.write( "Question 1197385: An ant moves on the following lattice, beginning at the dot labeled $A$. Each minute he moves to one of the dots neighboring the dot he was at, choosing from among its neighbors at random. What is the probability that after $5$ minutes he is at the dot labeled $B$? Image is attached below. \n" ); document.write( "

Algebra.Com's Answer #830622 by ikleyn(52781) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "

\r\n" );
document.write( "\r\n" );
document.write( "Let E denotes one step horizontally in (+) direction (East)\r\n" );
document.write( "    W denotes one step horizontally in (-) direction (West)\r\n" );
document.write( "    N denotes one step vertically   in (+) direction (North)\r\n" );
document.write( "    S denotes one step vertically   in (-) direction (South).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "We will denote each path as a sequence of letters E, W, N, S.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "To get from A to B in 5 steps, the path must contain 5 letters; equal number of E and W letters;\r\n" );
document.write( "                        in addition, the number of N letters must be 1 more than the number of S letters.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, all good paths must fall into one of these DISJOINT categories\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    (1) no E,W at all; there are only all distinguishable permutations of 3N and 2S.\r\n" );
document.write( "                       the number of such arrangements is   =  = 10. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    (2) one E compensated by one W, in any order; the rest are 2N and 1S in any arrangement.\r\n" );
document.write( "                       the total number of such arrangements is  =  = 60.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    (3) two E compensated by two W, in any order; and only one N; no S\r\n" );
document.write( "                       the total number of such artranjements is  =  = 30.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Thus, there are 10 + 60 + 30 = 100 good arrangements (paths leading from A to B).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The total number of all possible paths of the length 5 is  = 1024: any of 4 letters in each of 5 positions, independently.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So the probability is  P =  =  = 0.09766  (rounded).    ANSWER\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "--------------\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Nice contest/entertainment problem of a Math Olympiad or Math Circle level.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "As a pre-requisite, you must know everything about distinguishable permutations.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "About it, read the lesson\r
\n" ); document.write( "\n" ); document.write( " - Arranging elements of sets containing indistinguishable elements \r
\n" ); document.write( "\n" ); document.write( "in this site.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "/////////////\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "In this post, the diagram attached by the visitor at the end,
\n" ); document.write( "DOES NOT correspond to the wording part of the problem - it creates misunderstanding.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "In this problem, much wider lattice should be considered - otherwise, the probabilities
\n" ); document.write( "would not be all equal to 1/4 for moving one step from each current point.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );