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.
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ I think its from this site betterexplained.com/articles/… $\endgroup$– user56760Feb 27, 2019 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, 2019 at 6:11
-
$\begingroup$ Related: en.wikipedia.org/wiki/Taxicab_geometry $\endgroup$– beppe9000Feb 27, 2019 at 22:26
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
This is, I'm sure, answered somewhere else. It is also related to Pascal's triangle.
Simply fill out the grid as follows:
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.
answered Feb 27, 2019 at 3:37
-
$\begingroup$ This tip is also mentioned in MathCounts Mini #89 $\endgroup$ Feb 28, 2019 at 3:38
$\begingroup$
$\endgroup$
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$$
$\begingroup$
$\endgroup$
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$$
$\begingroup$
$\endgroup$
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
