Difference between revisions of "1977 Canadian MO Problems/Problem 7"

(Created page with "== Problem == A rectangular city is exactly <math>m</math> blocks long and <math>n</math> blocks wide (see diagram). A woman lives on the southwest corner of the city and works ...")
 
m (Problem)
 
Line 6: Line 6:
 
twice. Show that the number <math>f(m,n)</math> of different paths  she can take to work satisfies <math>f(m,n)\le 2^{mn}</math>.
 
twice. Show that the number <math>f(m,n)</math> of different paths  she can take to work satisfies <math>f(m,n)\le 2^{mn}</math>.
  
<math>\underbrace{ \left \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c| }
+
<math>\underbrace{ \left. \begin{array}{|c|c|c|c|c|c|c|c|c|c|c| }
 
     \hline
 
     \hline
 
     &&&&&&&&&& \\ \hline
 
     &&&&&&&&&& \\ \hline
Line 15: Line 15:
 
     &&&&&&&&&& \\ \hline
 
     &&&&&&&&&& \\ \hline
 
     &&&&&&&&&& \\ \hline
 
     &&&&&&&&&& \\ \hline
\end{tabular}
+
\end{array}
\right \}n}_m</math>
+
\right\}n}_m</math>
  
 
== Solution ==
 
== Solution ==

Latest revision as of 20:14, 10 March 2015

Problem

A rectangular city is exactly $m$ blocks long and $n$ blocks wide (see diagram). A woman lives on the southwest corner of the city and works in the northeast corner. She walks to work each day but, on any given trip, she makes sure that her path does not include any intersection twice. Show that the number $f(m,n)$ of different paths she can take to work satisfies $f(m,n)\le 2^{mn}$.

$\underbrace{ \left. \begin{array}{|c|c|c|c|c|c|c|c|c|c|c| }      \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline      &&&&&&&&&& \\ \hline \end{array} \right\}n}_m$

Solution