7
$\begingroup$

Starting with the A on top and only moving one letter at a time down to the left or down to the right, how many different paths from top to bottom spell ALGEBRA?

      A
     L L
    G G G
   E E E E
  B B B B B
 R R R R R R
A A A A A A A
$\endgroup$
7
$\begingroup$

Have you ever seen Pascal's Triangle? Each element in it is made by adding the two numbers directly above it.

            1
           1 1
          1 2 1
         1 3 3 1
        1 4 6 4 1
      1 5 10 10 5 1
     1 6 15 20 15 6 1

One interesting property of the triangle, is that if you use the rules you stated, each element's value denotes how many ways there are to get to that position from the top

So all you need to do is to add together all the entries of row 7, which will give you how many unique ways there are to go from row one to row 7 following your stated rules.

$$1 + 6 + 15 + 20 + 15 + 6 + 1 = 64$$

BTW, there is a formula for summing an entire row, because the total value of the row essentially doubles every time you go one down. So

$$\sum = 2^{rowNumber-1}$$

If you want to know more about how it works: TED-Ed Video

$\endgroup$
2
  • 1
    $\begingroup$ I'd love to see the video, but the link's not working (says page not found). Do you have any other link to that? Thanks. $\endgroup$ – space Mar 8 '16 at 15:49
  • $\begingroup$ @Helena i think if you search "Ted-Ed Pascal's Triangle" you should get it as the top result on youtube (or google, for that matter) :) $\endgroup$ – Second Wind Mar 8 '16 at 19:53
3
$\begingroup$

The answer is $64$. In fact for any $n$ letter word, the answer will be $2^{n-1}$.

We can prove this by induction:

  1. The base case for $n=1$ is trivially true with exactly one way.
  2. Consider any element $(i,j)$ in the pyramid. For any such cell there are two paths we can take, go left or go right, hence if the number of ways to reach $(i,j)$ is $m_{i,j}$, then total number of ways to reach row $i+1$ will increase by $2*m$ for all $j \in [1,i]$. This total will be $\sum_{j=1}^{i} 2 \times m_{i,j}$. Via the induction assumption we know that this sum is $\sum_{j=1}^{i} m_{i,j} = 2^{i-1}$. Thus the total number of ways to reach row $i+1$ is $2^{i}$.

    Q.E.D.

Interestingly, the number of ways to reach two columns in the same row of the pyramid are not necessarily the same. But the sum of the number of ways to reach all such columns in a particular row will always add up to a power of $2$. This is due to the fact the number of ways to reach $(i,j)$ is actually the binomial coefficient $\binom{i}{j}$ and $\sum_{i=0}^{n} \binom{n}{i} = 2^n$

$\endgroup$
1
$\begingroup$

Simply put, at any given point you have two choices, left or right. The number of the paths is therefore $2^6$.

$\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.