document.write( "Question 1201865: The following 7 × 22 grid is divided into squares that are 1 unit by 1 unit.
\n" ); document.write( "WebAssign PlotThe shortest possible path on this grid from A to B is 29 units long. One such path is shown in the figure. Let X be the set of all 29-unit-long paths from A to B.\r
\n" ); document.write( "\n" ); document.write( "Compute |X|, the number of 29-unit-long paths from A to B.
\n" ); document.write( "|X| = \n" ); document.write( "

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

You can put this solution on YOUR website!
.
\n" ); document.write( "The following 7 × 22 grid is divided into squares that are 1 unit by 1 unit.
\n" ); document.write( "The shortest possible path on this grid from A to B is 29 units long.
\n" ); document.write( "One such path is shown in the figure. Let X be the set of all 29-unit-long paths from A to B.
\n" ); document.write( "Compute |X|, the number of 29-unit-long paths from A to B.
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Indeed, the figure is not shown, and it can perplex a reader.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "But notice that 29 = 7 + 22, and it makes the meaning of the problem UNIQUE even without a plotted figure.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "The points A and B are opposite vertices of the 7x22 rectangle
\n" ); document.write( "and the shown path is a path on the grid, comprised of vertical and horizontal segments
\n" ); document.write( "of the grid from corner A to corner B, such that a path represents
\n" ); document.write( "a piece-wide monotonic function.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "For better understanding, this grid has 7 segments in one direction and 22 segments in other direction;
\n" ); document.write( "but the number of the vertices of the grid is (7+1) = 8 in one direction and (22+1) = 23 in the other direction.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "We can think that 22 segments of the grid are horizontal and 7 segments are vertical,
\n" ); document.write( "and A is the left lowest corner of the grid, while B is the upper right corner.
\n" ); document.write( "So, we can think that the associated function is a piece-wide monotonically increasing.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "The meaning of the problems remains the same at any other disposition of the grid
\n" ); document.write( "and the corners A and B.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Notice that vertical increments of the function are not necessary one vertical segment
\n" ); document.write( "of the grid: it can be two segments or three etc., but the governing rule is that the
\n" ); document.write( "associated function is a piece-wide MONOTONIC - it provides the shortest path.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Then it becomes CLEAR that this problem is the same as to ask,
\n" ); document.write( "in how many ways 22 (undistinguishable) objects can be distributed (placed) in 8
\n" ); document.write( "distinguishable boxes in a way that the empty boxes are allowed.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "In other words, it can be re-formulated in this way: how many solutions this equation\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " $\"x%5B1%5D\"$ + $\"x%5B2%5D\"$ + $\"x%5B3%5D\"$ + $\"x%5B4%5D\"$ + $\"x%5B5%5D\"$ + $\"x%5B6%5D\"$ + $\"x%5B7%5D\"$ + $\"x%5B8%5D\"$ = 22 (1)\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "may have in integer non-negative numbers $\"x%5Bi%5D\"$ , i = 1, 2, 3, . . . , 8.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "In this form, it is a typical problem to be solved by the \"stars-and-bars\" method.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "About this method, see this Wikipedia article \r\n" );
document.write( "\r\n" );
document.write( "https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "or my lesson\r\n" );
document.write( "\r\n" );
document.write( "    - Stars and bars method for Combinatorics problems \r\n" );
document.write( "\r\n" );
document.write( "in this site.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The answer is THIS: the number of solutions to equation (1) is  \r\n" );
document.write( "\r\n" );
document.write( "     =  =  = 1560780.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "ANSWER.  The number of paths in this problem is  1560780.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );