Each small square has a side length of one unit. How many distinct paths of six units are there from A to B? Draw a 6 x 6 square. On the bottom, left-hand corner of it write A. On the top, right-hand corner of it write B.

Guest Mar 12, 2015

#18**+5 **

CPhill, you didn’t miss anything. In this case, you caught something – the error in the binomial formula. (Now corrected and noted).

My CDD flare-ups are probably permanent, but the contagion is contained thanks to you.

Along with correcting the errors I clarified the maths formula by making it more consistent and uniform.

Nauseated
Mar 15, 2015

#1**0 **

Interesting question.

It looks as though no matter which route you take, you must take 12 steps. Each step has 2 choices. My guess would be:

$${{\mathtt{2}}}^{{\mathtt{12}}}$$=4096 different routes.

Guest Mar 12, 2015

#3**0 **

Don't believe him. Anon **is** more **full** **of s**t** than a Christmas goose!

The question states "How many distinct paths of **six** units" Anon changes it to 12.

Guest Mar 12, 2015

#4**+5 **

It is more than 6 units from A to B if you go in a straight line.

the diagonal of this square is

$${\sqrt{{\mathtt{36}}{\mathtt{\,\small\textbf+\,}}{\mathtt{36}}}} = {\mathtt{8.485\: \!281\: \!374\: \!238\: \!570\: \!3}}$$

So there are definitely NO paths that are only 6 units in length!

Melody
Mar 13, 2015

#5**+5 **

All 6-unit paths from A to B are 3 up and 3 across. Just choose 3 of the 6 (This pertains to 6-unit paths only. Not 12 unit paths, or 9-unit paths, or the path of a Christmas goose).

$$\; Solution: \\\\

\left( {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right) = \dfrac{{n!}}{{k!\left( {n - k} \right)!}}\; \hspace{15pt}| \hspace{15pt} \Text {n=6 \; k=3} \\

\left( {\begin{array}{*{20}c} 6 \\ 3 \\ \end{array}} \right) \; = \; 20 \; \tezt {paths}\\$$

Nauseated
Mar 13, 2015

#6**+5 **

I'll bite!

To traverse the square don't you follow the line around the edge if it is a path? Considering this, does't each square require two choices?

Guest Mar 13, 2015

#7**+5 **

The instructions definitely say to draw a 6x6 square. So there are no "3 up and 3 across" routes.

Christmas Goose indeed!

Guest Mar 13, 2015

#8**0 **

You must travel on the line, not on the square. Why else would you start at point A, which is the lower left? It does not say to start at the lower left block.

Guest Mar 13, 2015

#9**0 **

It does not ask you for the shortest route, it asks for the number of distinct routes!

Guest Mar 13, 2015

#10**+5 **

The above answer was used for a similar question on another forum. That grid was 3X3 instead of 6X6. (That may have been what was intended). CDD aside, the posted solution is accurate for a 3X3 grid.

However, this question as stated does posit inconsistent restrictions.

**Melody is correct. There are no 6 unit solutions. **

Nauseated
Mar 13, 2015

#11**+5 **

I do hope that you have not passed on your CDD infection to other members of the forum Nauseated!

**If any of us get CDD we will know exactly who to blame!**

-------------------------------------------------------------------

On a more serious note I am going to give your 3 by 3 solution more thought.

I have not fathomed Nauseated's answer (perhaps he can better explain)

but I did it a different way and got the same answer.

This is how I did it.

I thought of it as three ladders placed side by side.

There is the ground level - L1

the first rung L2

the second rung L3

and the top rung L4

So you have to be on each of the ladders and you can not go down a rung between ladders or you will not get to the end point in 6 units.

So here are your 'rung' possibilities as you go across the ladders.

L1 L1 L1,2,3 or 4 4 possibilities

L1 L2 L2,3 or 4 3 possibilities

L1 L3 L3 or 4 2 possibilities

L1 L4 L4 1 possibilities

L2 L2 L2,3,or 4 3 possibilities

L2 L3 L3, or 4 2 possibilities

L2 L4 L4 1 possibilities

L3 L3 L3 or 4 2 possibilities

L3 L4 L4 1 possibilities

L4 L4 L4 1 possibilities

Total = 20 possibilities

NOW Nauseated, can you explain why our 2 answers are the same.

Do you actually understand the logic behind your answer? If so, please share

Melody
Mar 14, 2015

#12**+5 **

I cannot prove this......but just fooling around, I noticed the following pattern.....

If we have a square.....there are 2 distinct paths of 2 units in length = 1 1 the first row of Pascal's Triangle {I'm calling the single 1 at the top of the Triangle, Row 0 }

To make this follow a pattern, I will write this as 0 1 1 0 ..... notice that the "middle" two numbers sum to 2

Now....it we have 2 x 2 squares = 4 squares....the number of distinct paths of 4 units in length = 6 {prove this for yourself}

Notice that this is the sum of the middle two numbers of the the third row of Pascal's triangle 1 3 3 1

And if we have 3 x 3 squares = 9 squares......the number of distinct paths of 6 units in length = 20

Notice that this is the sum of the middle two numbers of the 5th row of Pascal's Triangle 1 5 10 10 5 1

This makes me wonder that if we have 4 x 4 squares = 16 squares.....that the number of distinct paths of 12 units in length will equal 70.....in other words the sum of the middle two numbers in the 7th row of Pascal's Triangle

1 7 21 35 35 21 7 1 (????? )

The pattern for the number of distinct paths in an n x n arrangement appears to be 2 * C(2n-1, n) for n > 1

Can someone prove/disprove this???

CPhill
Mar 14, 2015

#13**+5 **

"This makes me wonder that if we have 4 x 4 squares = 16 squares.....that the number of distinct paths of **12 units** in length will equal 70.....in other words the sum of the middle two numbers in the 7th row of Pascal's Triangle "

Should that have been 8 units Chris ?

Melody
Mar 14, 2015

#15**+5 **

**The general formula is**

$$\left( {\begin{array}{*{20}c} 2N \\ N \\ \end{array}} \right) = \dfrac{{(2N)!}}{{N! (2N-N)!}}\; \hspace{15pt}\leftarrow \hspace{15pt} \tiny \textcolor[rgb]{1,,0}{\text {(Corrected error in binomial formula)}}\\$$

**This works for all square grids from N=1 to any finite number.**

** **

A single square is

$$\left( {\begin{array}{*{20}c} 2(1) \\ 1 \\ \end{array}} \right) = \; 2\\$$

(one unit up and one unit right, or one unit right and one unit up).

**This can be extended to a non-square grid of (R * C) where R and C are rows and columns.**

For this the general formula is

$$\left( {\begin{array}{*{20}c} R+C \\ C \\ \end{array}} \right)\;=\;

\dfrac{{(R + C)!}}{{R!\; C!}} \;=\; \text {unique\;paths}

\hspace{15pt}\leftarrow \hspace{15pt} \tiny \textcolor[rgb]{1,,0}{\text {(Corrected \& clarified )}}\\$$

I lack the skills to demonstrate a formal maths proof. Here’s the basic logic:

In a square grid of size N when the number of units between diagonal corners is set to equal 2N, half the route will compose the X direction and half will compose the Y direction. The position of the square (X or Y) determines the position of subsequent squares (X or Y). The value of interest is the unique routes consisting of equal X and Y directions, this is found by “choosing the N positions from the 2N that are available.

(The solutions are close to the number of ways to catch CDD).

$$\tiny \textcolor[rgb]{1,,0}{\text {(Edited: Corrected errors \& clarified )}}\\$$

Nauseated
Mar 14, 2015

#16**0 **

Thanks Chris and Nauseated.

I shall have to have a really proper look when it is not after 3:30am :)

Melody
Mar 14, 2015

#17**+5 **

Nauseated.....how does C(2N, N) = (2N)!/N! ???

My guess of 70 unique routes wth a 4 x 4 square is actually the same as your formula of C(8, 4) = 70

I had forgotten that, in Pascal's tirangle, the summing of the middle two terms in the 7th row would actually produce the 5th term in the 8th row, ie., C(8,4).....thus......your result appears justified.....

But (2*4)! / 4! = 8! / 4! = 1680 routes ???? Shouldn't there be an additional (2N - N)! in the denominator??

Am I missing something...or.....is premature CDD actually here to stay???

BTW.....I like your logic......!!!

CPhill
Mar 15, 2015

#18**+5 **

Best Answer

CPhill, you didn’t miss anything. In this case, you caught something – the error in the binomial formula. (Now corrected and noted).

My CDD flare-ups are probably permanent, but the contagion is contained thanks to you.

Along with correcting the errors I clarified the maths formula by making it more consistent and uniform.

Nauseated
Mar 15, 2015