## Interview Question

Trading Analyst Interview Los Angeles, CA

`Madison Tyler Holdings`

## Assume that on a chessboard, the King piece is on tile E

1 (bottom row, 5 columns across). It can move straight forward, forward diagonally to the left, or forward diagonally to the right on each move. How many different paths can it take to get to tile E8 (top row, five columns across) in exactly 7 moves?

## Interview Answer

4 Answers

I don't think IC is correct. I haven't gone through your methodology, but I think the answer is larger.

The piece moves forward each turn. It moves either left, right or straight ahead.

Take left=-1, right=+1, straight=0.

The sum of 7 such numbers must be 0. Therefore, at least one move must be straight ahead.

There are four types or routes.

a 0x+1, 0x-1, 7x0

b 1x+1, 1x-1, 5x0

c 2x+1, 2x-1, 3x0

d 3x+1, 3x-1, 1x0

there is only 1 route of type a

there are 7x6 of type b, etc.

a 1

b 7x6=42

c 7x6x5x4=840

d 7x6x5x4x3x2=5040

a+b+c+d=5923

Am I wrong?

Yes I was wrong. IC was right.

there is only 1 route of type a

there are 7x6 of type b, etc.

there are ((7x6)/2)x((5x4)/2)=210 of type c

there are ((7x6x5)/6)x((4x3x2)/6)=140 of type d

giving a total of 393

Using permutations.

You can see the problem as such: any move you make to the left has to be compensated by move to right. I have to go up 7 tiles total. With R representing a right move, L a left move and A a move straight ahead, my possible combinations are:

1) AAAAAAA

2) RLAAAAA

3) RRLLAAA

4) RRRLLLA

One now has to compute all the permutations which is fairly straightforward:

we have 1 + 7!/5! + 7!/(3!x2!x2!) + 7!/(3!x3!)

which is: 1 + 42 + 210 + 140 = 393

This

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

393

126 141 126

30 45 51 45 30

4 10 16 19 16 10 4

1 3 6 7 6 3 1

1 2 3 2 1

1 1 1

K

K is the starting spot for the king. There is 1 way to get to each of the tiles in the row right above K. For the row above the row of 1-1-1, the number of paths to each tile is the sum of the possible paths to each tile that leads to it. (ie, for the first 2 in that row, you can get to it from either of the first two 1s in the row below). This is basically a 'trinomial' expansion as each number is the sum of the 3 numbers directly below it.

This continues until the 8th row (where the diamond formation tapers inward since the number of left moves must equal the number of right moves in order to end up in the same column (E) where the King started)

The final answer is 393 as demonstrated in the diagram above. It took me well over 30 minutes to get it, and the interviewer had lost all interest by that point. He was still nice in making sure to explain the methodology and ensuring that I arrived at the right answer, but was quick to hang up once the solution had been determined.

Aug 17, 2011