3
$\begingroup$

Suppose you're on a 4 × 6 grid, and want to go from the bottom left to the top right. How many different paths can you take? Avoid backtracking -- you can only move right or up.enter image description here

$\endgroup$
  • 3
    $\begingroup$ I think its from this site betterexplained.com/articles/… $\endgroup$ – user56760 Feb 27 at 3:32
  • 6
    $\begingroup$ (In the future please be aware that for content you did not create yourself, proper attribution is required. You need to include (at minimum) where it came from—and any additional context you can provide is often helpful to solvers. Posts which use someone else's content without attribution are generally deleted.) $\endgroup$ – Rubio Feb 27 at 6:11
  • $\begingroup$ Related: en.wikipedia.org/wiki/Taxicab_geometry $\endgroup$ – beppe9000 Feb 27 at 22:26
21
$\begingroup$

This is, I'm sure, answered somewhere else. It is also related to Pascal's triangle.

Simply fill out the grid as follows:

enter image description here

In this grid, each number represents the number of ways of getting to that particular intersection. And that number is precisely the number of ways to get to the intersection below it added to the number of ways to get to the intersection to the left of it.

$\endgroup$
  • $\begingroup$ This tip is also mentioned in MathCounts Mini #89 $\endgroup$ – MilkyWay90 Feb 28 at 3:38
15
$\begingroup$

A more mathematically oriented answer:

You have $10$ moves to make in total and you need to choose which $4$ of them are going to be up. The number of ways to do that is $${10\choose 4}=210$$

$\endgroup$
1
$\begingroup$

Here is a small python program which solves it. Every step we can go up or right with the goal being 4,6.

def count(up, right):
    if up > 4:
        return 0 
    if right > 6:
        return 0
    if up == 4 and right == 6:
        return 1 
    return count(up + 1, right) + count(up, right + 1)
print count(0,0)

output : 210

$\endgroup$
0
$\begingroup$

Write them out. Start with

rrrrrruuuu
rrrrruruuu
rrrrruuruu
...
uuuurrrrrr

and then count them up. You should have 210 in total.

Or:

$$\binom30+\binom41+\binom52+\binom63+\binom74+\binom85+\binom96$$ $$=1+4+10+20+35+56+84$$ $$=210$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy