25
$\begingroup$

I'm prepping for the GRE.

Would appreciate if someone could explain the right way to solve this problem. It seems simple to me but the site where I found this problem says I'm wrong but doesn't explain their answer. So here is the problem verbatim:

enter image description here

Find the number of paths from x to y moving only right (R) or down (D).

My answer is 6. What am I missing??

Thanks for any help.

$\endgroup$

13 Answers 13

53
$\begingroup$

The solution to the general problem is if you must take $X$ right steps, and $Y$ down steps then the number of routes is simply the ways of choosing where to take the down (or right) steps. i.e.

$$ \binom{X + Y}{X} = \binom{X + Y}{Y} $$

So in your example if you are traversing squares then there are 5 right steps and 1 down step so:

$$ \binom{6}{1} = \binom{6}{5} = 6 $$

If you are traversing edges then there are 6 right steps and 2 down steps so:

$$ \binom{8}{2} = \binom{8}{6} = 28 $$

$\endgroup$
  • $\begingroup$ It may be worth noting for the OP that a similar method works if $x,y$ are in $n$-dimensional space. $\endgroup$ – Meow Jan 17 '14 at 17:49
23
$\begingroup$

If you panic during the test, consider just drawing it as a Pascal's triangle

Where

  • Value at the origin (x) is 1
  • For all other nodes, the value is the sum of its top and left neighbors

Pascal's triangle

$\endgroup$
  • $\begingroup$ interesting thanks! $\endgroup$ – Grijesh Chauhan Jan 13 '14 at 10:11
  • 1
    $\begingroup$ How do we explain this? $\endgroup$ – Ravi Sanwal Jan 9 '18 at 9:00
20
$\begingroup$

Any such path is a permutation of 6 R and 2 D, so the answer is $${6+2\choose 2}={8\choose 2}=\frac{{8 \times 7}}{2}=28$$

$\endgroup$
  • 2
    $\begingroup$ maybe this is the answer traveling along edges $\endgroup$ – janmarqz Jan 12 '14 at 20:03
  • $\begingroup$ there goes my +1 'cuz this has to do with the Catalan numbers :D $\endgroup$ – janmarqz Jan 12 '14 at 20:05
  • $\begingroup$ Exactly janmarqz! This rectangle is called a 7 by 3 grid, so the traveling is along vertices on line segments. $\endgroup$ – Woria Jan 12 '14 at 20:07
  • 3
    $\begingroup$ I agree, this could have been clearer, but the $x$ and $y$ seem to mark lattice points, not squares. $\endgroup$ – Carsten S Jan 12 '14 at 20:17
14
$\begingroup$

To get from point x (not square x) to point y there are $8$ steps to be taken. $2$ of them downwards and $6$ to the right. So it just comes to electing exactly $2$ of the $8$ consecutive steps to be the steps downwards.

Picking $2$ out of $8$ can be done on $\binom{8}{2}=28$ ways.

When you are thinking in squares instead of points then there $6$ steps to be taken. $1$ of them downwards and $5$ to the right. So it just comes to electing exactly $1$ of the $6$ consecutive step to be the steps downwards.

Picking $1$ out of $6$ can be done on $\binom{6}{1}=6$ ways.

That explains the fact that your answer was $6$.

$\endgroup$
  • $\begingroup$ So the lesson is to look carefully at what is being asked. In this case movement between vertices rather then hops between squares, and vertices because you have to assume based on the diagram that X and Y refer to vertices not squares. Seems like an easy mistake to make. $\endgroup$ – user120865 Jan 12 '14 at 20:30
  • $\begingroup$ Indeed. A good look at what is being asked is beyond doubt always the best start to solve the problem. $\endgroup$ – drhab Jan 12 '14 at 20:37
9
$\begingroup$

See here you can easily compute the number of paths by applyinfg the COMBINATION concept.

So what is the concept!!

ok then.....let us consider to proceed from x to y we have to take the steps to the direction of RIGHT and DOWN....fine?

and let us take RIGHT = R and DOWN = D.....still fine.. :-)

now see if anyone wants to go from X to Y he must take 2 DOWN steps and atmost 6 RIGHT step.

So we can say that we have to take total 8 numbers of step.You can check it by your own that we must take 8 steps to reach at Y starting from X poit.ok.

and see here we can write a combination of steps,like: { R-R-R-R-D-R-D-R } -----(see its a suitable traverse path.match this path with the picture.)

And now we can make our main observation on this problem.....So what is it? See, you have to take total of 8 steps and all of them are the combination of R and D's ok?

And the observation is: You have to take just 2 D(DOWN step) and also just 6 R(RIGHT step) to reach at Y.

So we can say that the total number of combination is: HOW MANY COMBINATION OF 'R' OR 'D' is possible from the total of 8 steps!!!!!

The required answer is actually the combination of 2 PLACES for D's OR 6 PLACES for R's from 8 total steps(OR TOTAL 8 PLACES where R and D letters take place)........

see here we are just mapping our problem of counting the number of suitable paths from X to Y into a basic counting problem.....And we just logically made a connection between these two problems and it is clear that if we can calculate the combination of 2 PLACES for D's OR 6 R's from total 8 steps it will be enough!!

Here is the total of 8 places where D and R may take places:

{ ___  ___  ___  ___  ___  ___  ___  ___ }

And we actually CHOOSE 2 places for for 2 D's OR we CHOOSE 6 places for 6 R's but we dont bother for the oreding of D's OR R's.....the 2 D's OR the 6 R's can tale place randomly but their requirement for the places is fixed!! it is 2 for 2 D's and it is 6 for 6 D's......actually choosing 2 D's OR 6 R's are basically same!! :-)

So, the answer is : 8C2 or 8C6 (note that both are same!! :-) ) 8C2 = 28 and easily you can see 8C6 = 28.

SO, THERE ARE 28 PATHS FROM X TO Y!!

$\endgroup$
  • $\begingroup$ you have read the whole answer given by me!nice...and it is my pleasure to help you. $\endgroup$ – arkadeep Jan 12 '14 at 20:57
4
$\begingroup$

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\down}{\downarrow}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\ot}{\downarrow}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ In general we have steps to right and down. Tipically, this is a possible path: $$ {\Huge \to\ \to\ \down\ \to\ \to\ \to\ \down \to} $$ In general, the problem is reduced to put two down arrows $\down$ in 8 sites like the following example: $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ &&&&\down&&\down \end{array} $$ Let's put one $\down$ at the first step, then we have $\color{#ff0000}{\large 7}$ positions left to put the other one. Next, we put the first $\down$ at the second step and we have $\color{#ff0000}{\large 6}$ position left to put the other one and so on such that $7 + 6 + 5 + 4 + 3 + 2 + 1 = \color{#0000ff}{\Large 28}$ which is $\ds{8 \choose 2}$.

$\endgroup$
3
$\begingroup$

Check this handcrafted portable network graphic : enter image description here

$\endgroup$
  • 2
    $\begingroup$ You walk on the squares, but they want you to walk on the black lines. $\endgroup$ – Jeppe Stig Nielsen Jan 12 '14 at 21:08
  • $\begingroup$ yes, this is the interpretation in the OP. Others are explained aside. $\endgroup$ – janmarqz Jan 13 '14 at 2:43
3
$\begingroup$

First note that you will always be moving 6 squares right and 2 squares down, just because $y$ is 2 squares down and 6 squares to the right from $x$.

Next, note that a different ordering of these steps will always result in a different path. Then, the question simply becomes how many ways there are to arrange 6 "right steps" and 2 "down steps" from first to last.

This is equal to the total number of ways to arrange 8 steps ($= 8!$), divided by the number of different ways that are accounted for by some of the steps being the same ($6!$ for 6 right steps and $2!$ for 2 down steps), which is $\displaystyle \frac{8!}{6!2!} = 28$.

If you're moving only 5 squares right and 1 square down, which is the case if you're moving on the insides of squares rather than the intersections of grid lines, then you're arranging 6 total steps, 5 right and 1 down, which gives the formula $\displaystyle \frac{6!}{5!1!} = 6$.

$\endgroup$
2
$\begingroup$

Others have come up with similar alternative solutions but I'll try to be more concise:

  • To get from $x$ to $y$ you need to take 6 steps to the $R$ight and 2 to $D$own.
  • What separates one solution from another is just the order in which you take the steps. Example: $RRDDRRRR$ is different from $RRDRRRRD$.
  • So our problem boils down to counting how many different orders are possible. For a 8 letter word, the solution is $8!$. But note that in the examples above you could switch any two Rs or the two Ds and noone would notice. We therefore divide by the possible combinations of these letters, that is $6!$ and $2!$.
  • Our solution is $\frac{8!}{2!6!} = \frac{8\cdot 7 \cdot 6!}{2!6!} = \frac{8\cdot 7}{2\cdot 1} = 28$.

PS.

To get the logic of number of reordering of letters, try to play with simple words such as $dog$, $doggy$, $moon$.

$\endgroup$
  • $\begingroup$ Can you expand how 8! = 8*7 and 2!6! = 2 * 1 $\endgroup$ – CSharper Aug 13 '16 at 19:05
  • 1
    $\begingroup$ I added an extra step.. but basically you use that $8! = 8*7*(6*5*4*3*2*1) = 8*7*6!$ and then the $6!$ cancel. $\endgroup$ – snoram Aug 13 '16 at 19:10
2
$\begingroup$

I believe you have $28$ ways really. I give you $27$ and try to find out the only absent in the figure below

enter image description here

$\endgroup$
  • $\begingroup$ Is it...3R,2D,3R...starting from X?? It's the only one that has the same complementary path from Y $\endgroup$ – Carrick Jan 6 at 6:55
1
$\begingroup$

Well you can do only down and right($6$ right and $2$ down)

Now if we show the way we get to $8$ digit word that has $2$ and $6$ similers

We can change the place of $8$ digits to make $8!$ different words.But there are duplicate cases the similar $6$ digits can be change without making any new words that we should divide the answer to $6!$also that two similar digits can changed without making any new words which means we should also divide it by $2!$ which gives:

$\frac{8!}{6!2!}=\frac{56}{2}=28$

$\endgroup$
1
$\begingroup$

i see alot of good explanations but in my opinion the most useful and simple answer is for any nxm matrix using the down or right rule there are $${(n-1)+(m-1)\choose(m-1)}$$ paths.

$\endgroup$
0
$\begingroup$

28 is the answer. As,from x to y,there are 2 downward steps and 6 horizontal,rightward steps, so,going by the general formula

                    ***{(m+n)!}/{(m!n!)}***
                     =>{(2+6)!}/{2!6!}
                     =>{8!}/{2!6!}
                     =>**28**

Hence,this is the required answer.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.