Jane Street

## Interview Question

## Interview Answer

7 Answers

741.

Hint: Partition the board into rows (or columns if you wish). How many moves end on the 0th row? How many on the 1st ... on the 20th?

Well, if you needed a good quick upper bound, you could say $$8^{10}$$, but since they are probably looking for something more reasonable, I would first bound the area within which the knight can move.

If we were to actually draw out the shape, it would look like a 4 sided jagged staircase polygon, but we can make a rough (over)estimate by assuming that from it's starting position, a knight can move no farther than sqrt(500) radius since each move is sqrt(5) ----> a circle of area 500*pi squares ~ 1570-1575 squares (3.14 < pi < 3.15)

After 10 moves or any even number of moves, the knight must land on a square with the same color as the square it started on, so that reduces the area by 1/2, leaving a maximum of 738 squares left (still an overestimate).

The final answer is odd because we know by symmetry that if we reflect any reachable position over the knight's starting position, we will get another reachable position; however, this excludes the knight's starting position, which is a reachable position since after 5 moves we can always retrace back to it.

So I would say 737 is a pretty good estimate.

That would make sense, but 1/2 * {1570, 1575} = {785, 788}, not a max of 738.

Thanks a bunch though!

Solution visualised : http://twitpic.com/9jegtb

Formula (no idea why, but it works)

x=amount of steps

(square(1+4*x) + 1) / 2 - square(4*x) / 16

Range as square : ( 2x + 1 + 2x ) * (2x + 1 + 2x) = 41*41 = 1681

Add centerpoint : + 1 / 1682

Only half of the fields will be posible : / 2 = 841

Corners are not reachable, 1/8th of each direction without center lines : ( 2x*2x / 2 ) /8 = 100

I don't understand the question :(

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

After n moves, the number of possible positions is (n+1)^2.

By connecting (0,n), (0, -n), (n, 0), (-n,0), we have a square. There are n+1 possible positions on an edge. And along one direction, there are n+1 lines which have possible positions(think about odd and even property).