Waste less time on Facebook — follow Brilliant.
×

Lovers Meet - Part 8

Anna and Ben live at opposite corners of a \(m \times n \) block.
If Anna only moves right or up or down, and isn't allowed to retrace her steps, how many ways does she have to get to Ben?

Note by Chung Kevin
2 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

m^(n-1)

Mobin Mithun - 2 years, 6 months ago

Log in to reply

Why?

Calvin Lin Staff - 2 years, 6 months ago

Log in to reply

(m+1)^n it is?

Shib Shankar Sikder - 2 years, 5 months ago

Log in to reply

Comment deleted Aug 19, 2015

Log in to reply

How would you generalize it to an \(m \times n \) board? And why is that the answer?

Calvin Lin Staff - 2 years, 6 months ago

Log in to reply

Start at the beginning. Anna can move right or down. If she moves down, she can only move down until she moves right. She can move to the second column in n+1 ways. The same case occurs for every column. Anna will have n+1 ways of moving to the next column each time. This keeps going until she is in the last column, in which case she has to move toward Ben. There are m+1 columns, each of which give n+1 ways of moving to the right, except for the last column. Therefore there m^(n+1) ways for Anna to reach Ben.

E Z - 2 years, 5 months ago

Log in to reply

Yes, that's the quick way to recognize it. Once you choose the horizontal paths (one in each column), then the vertical paths are fixed. This is why we can set up the bijection.

Chung Kevin - 2 years, 5 months ago

Log in to reply

Comment deleted Aug 03, 2015

Log in to reply

Close, but not quite. Look at the other parts, and see if the answer matches your guess of \( m+n \choose n \).

You are forgetting that Anna is allowed to move up and down (but not retrace her steps).

Calvin Lin Staff - 2 years, 5 months ago

Log in to reply

There are (m+1) ways to enter each column. Anna has to enter n such columns consecutively. So the number of ways is (m+1)(m+1).....upto n times, i. e. (m+1)^n. This comes up because she is not allowed to go left. If she could go right, left and down, answer would be (n+1)^m with (n+1) ways to enter each of the m rows (WLOG).

Shib Shankar Sikder - 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...