[bonanova]

Last month we asked for a particular on a chessboard.

We'll simplify, and deal in this puzzle with a robotic King. This robotic King moves, as Kings do, one square at a time, along the four compass points, at a rate of one square per second. His journey is from QR1, the lower left square, to KR8, the upper right square, and back [retracing his exact path, and seeing to it that his trip takes the shortest possible time.] Immediately upon return, he repeats the journey, taking a different path. The King notes that it takes only about a half-day to travel all possible paths between the points. Being a robot, the King never has to pause to rest. Nevertheless, when he finishes, he does meander off his chessboard down to Morty's Tavern to enjoy a cold one with Alex and the boys.

One evening over a cool pint, Alex wondered aloud to the King, If ye spent not a half day but an entire year on these Kingly expeditions, how large of a square do ye think ye could explore? Davey overheard and quickly thought 8 x 365 / .5 and guessed, Maybe a 5000 x 5000 square? Ian thought a little longer, scribbled down SQRT [64 x 365 / .5] and quessed, Maybe a 200 x 200 square?

But Alex just winked, and suggested that the King might want to ask the BrainDenizens.

[Guest]

how large of a square do ye think ye could explore?

if by explore you mean go from one corner to another by all possible shortest routes

3432 steps one way

6864 Steps both ways

13728 steps per day

5010720 steps per year

(2x-2) C (x-1)<5010720

x=13 by 13 board?

[Guest]

an 8x8 board has 49 possible shortest paths from corner to corner, each taking 28 steps to complete (round trip).

49 paths * 28 seconds/path = 686 seconds or 22 minutes 52 seconds to complete an 8x8 board..

I don't see the half day to complete an 8x8 board (using shortest possible paths), but anyway:

if my logic above is right, then for an n x n board,

number of paths = (n-1)^2

time per path = 4*(n-1)

(n-1)^2*4*(n-1)=365*24*60*60, solve for n = 200

He should be able to cover a 200x200 board in a year (Hopefully our robotic king has a lithium-ion battery and not one of those crappy NiCad ones : ))

By the way - great puzzle! I love it!

Edited July 17, 2010 by littlej

[Guest]

the number of shortest path combinations = 14 C 7 = 3432

because there are 14 steps taken, 7 of which must be up

now when i multiply that by the number of steps taken there and back, 28 i get 96096 seconds = 26.7 hours

which is clearly not half a day

[Guest]

the number of shortest path combinations = 14 C 7 = 3432

because there are 14 steps taken, 7 of which must be up

now when i multiply that by the number of steps taken there and back, 28 i get 96096 seconds = 26.7 hours

which is clearly not half a day

I think you're right with the combination of paths - I was off.

He should be able to cover a 12x12 board in one year.

[2*(N-1) C (N-1)] * 4*(n-1)seconds for a board size of n

for N = 12 this = 31039008 which is less than 31556926s/year

for N = 13 this = 129799488 which is greater than 31556926s/year

therefor he can only make a 12x12 board

[bonanova]

littlej has it.

The OP was off by a factor 2 [the return trip].

There are 3432 x 14 x 2 = 96 096 moves for an 8x8 board, and only 86400 seconds in a day.

So it normally took the King a little more than a complete day, not a half-day.