Jane Street Interview Question: On an infinite chessboard, to... | Glassdoor

Trader Interview

# On an infinite chessboard, to how many possible positions

can a knight move after 10 moves (provide a 90% confidence interval)? Is the actual answer even or odd?
Answer

## Interview Answer

7 Answers

0

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).

torpedo on Jan 29, 2012
2

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?

anonymous on Jan 30, 2012
3

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.

Anonymous on Feb 2, 2012
0

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

Thanks a bunch though!

Anonymous on Mar 28, 2012
2

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

Aldwin on May 10, 2012
0

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

aldwinaldwin on May 10, 2012
0

I don't understand the question :(

Me on May 13, 2014

## Add Answers or Comments

To comment on this, Sign In or Sign Up.