<p>Consider the paths of length <img alt="$16$" height="13" src="https://latex.artofproblemsolving.com/9/a/5/9a5b4928c8fe50ce3c2428da3bee3505e891b788.png" width="17" /> that follow the lines from the lower left corner to the upper right corner on an <img alt="$8\times 8$" height="12" src="https://latex.artofproblemsolving.com/1/9/7/1970593e80703dfe31ef799575bae2ee9819ced1.png" width="40" /> grid. Find the number of such paths that change direction exactly four times, as in the examples shown below.</p> <p><img alt="[asy] size(10cm); usepackage("tikz");label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(2,0)--(2,3)--(5,3)--(5,8)--(8,8);\end{tikzpicture}",origin); label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(0,3)--(3,3)--(3,5)--(8,5)--(8,8);\end{tikzpicture}",E); [/asy]" height="198" src="https://latex.artofproblemsolving.com/2/d/c/2dcb0a2c52c662dbc003bf1192e85a32fb7d35d2.png" width="475" /></p>

Question No: 421

Consider the paths of length $16$ that follow the lines from the lower left corner to the upper right corner on an $8\times 8$ grid. Find the number of such paths that change direction exactly four times, as in the examples shown below.

$[asy] size(10cm); usepackage("tikz");label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(2,0)--(2,3)--(5,3)--(5,8)--(8,8);\end{tikzpicture}",origin); label("\begin{tikzpicture}[scale=.5]\draw(0,0)grid(8,8);\draw[line width=2,red](0,0)--(0,3)--(3,3)--(3,5)--(8,5)--(8,8);\end{tikzpicture}",E); [/asy]$

Editorial

Tags: Combinatorics

Question Details