wu :: forums
wu :: forums - Knight on an infinite chessboard

Welcome, Guest. Please Login or Register.
Jun 18th, 2018, 2:30am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, SMQ, Grimbal, towr, Icarus, Eigenray, ThudnBlunder)
   Knight on an infinite chessboard
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Knight on an infinite chessboard  (Read 6588 times)
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Knight on an infinite chessboard  
« on: Apr 15th, 2003, 12:01pm »
Quote Quote Modify Modify

Consider a knight on an infinite chessboard.  How many squares can it reach after precisely n moves?
IP Logged

Nick's Mathematical Puzzles
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13608
Re: Knight on an infinite chessboard  
« Reply #1 on: Apr 15th, 2003, 1:09pm »
Quote Quote Modify Modify

it might be 2^(2n+1)+n-1 but it's probably not..
(I only tried n=0,1,2 so far )
« Last Edit: Apr 15th, 2003, 1:11pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Re: Knight on an infinite chessboard  
« Reply #2 on: Apr 15th, 2003, 2:08pm »
Quote Quote Modify Modify

I would say f(0) = 1.  After no moves, it can only be on one square -- the square it starts from.
 
The knight can move back to a square it has moved from.
IP Logged

Nick's Mathematical Puzzles
cho
Guest

Email

Re: Knight on an infinite chessboard  
« Reply #3 on: Apr 15th, 2003, 2:22pm »
Quote Quote Modify Modify Remove Remove

It takes a few rounds to stabilize. It starts 1,8,33,76,129,196. From that point on each round grows by a number 14 greater than the previous. I'm not sure how to turn the whole sequence into one equation.
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Knight on an infinite chessboard  
« Reply #4 on: Apr 15th, 2003, 4:20pm »
Quote Quote Modify Modify

Quote:
It takes a few rounds to stabilize. It starts 1,8,33,76,129,196. From that point on each round grows by a number 14 greater than the previous. I'm not sure how to turn the whole sequence into one equation.  

I'm not sure what you mean there, cho.
 
Do you mean f(n) - f(n-1) = 14n + some constant ?
 
OR
 
Do you mean f(n) - f(n-1) = 14 ?
 
OR
 
Perhaps you mean something else?  
 
Why 14?
 
How did you get your sequence?
« Last Edit: Apr 16th, 2003, 4:56am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
cho
Guest

Email

Re: Knight on an infinite chessboard  
« Reply #5 on: Apr 15th, 2003, 6:13pm »
Quote Quote Modify Modify Remove Remove

Okay, I'm going to show my utter lack of math skills here. By instability I mean that moves 1 and 2 don't fit the pattern. If they did the sequence would be  
1,12,37,76,129,196,277,372,481...
Notice that the difference between adjacent values is
11,25,39,53,67... There's the 14.
The pattern is obvious, but my last math class was a basic algebra class in high school 30 years ago.  
How I got my sequence was by counting (very little math required). I took a piece of graph paper and marked out the possible locations for one quadrant and multiplied by 4:
0
3212343456567878
214323454567678 8
3232343456567878
232343454567678 8
3434345456567878
434345456567678 8
5454545656767878
454545656767878 8
56565656767878 8
6565656767878 8
767676767878 8
67676767878 8
7878787878 8
878787878 8
 8 8 8 8 8
8 8 8 8 8
IP Logged
cho
Guest

Email

Re: Knight on an infinite chessboard  
« Reply #6 on: Apr 15th, 2003, 6:20pm »
Quote Quote Modify Modify Remove Remove

I'm also assuming the question seeks the number of squares you could be sitting on on the Nth move, and not all the squares it has touched so far (only the same colored squares as the original square after an even number of moves, eg)
IP Logged
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: Knight on an infinite chessboard  
« Reply #7 on: Apr 17th, 2003, 4:51pm »
Quote Quote Modify Modify

Quote:
Personally, I think the function is more likely to be linear than exponential.
After a given number of moves, a knight can (approximately) reach any square within a "circle" of radius proportional to the number of moves.  The number of squares in that "circle" is approximately the area of the circle.  So it makes sense that, asymptotically, at least, the function would be quadratic.
 
Which is exactly what cho found, so this post is rather redundant now...
IP Logged
Netman
Guest

Email

Re: Knight on an infinite chessboard  
« Reply #8 on: Apr 23rd, 2003, 6:59pm »
Quote Quote Modify Modify Remove Remove

For the version where the knight cannot revisit squares... after wasting 12 CPU minutes bruteforcing the problem, I came to the realization that the only square that restriction eliminates is the starting square, all other squares can be reached via some sequence of moves.
 
So the equation:
f(n) = 7n2 + 4n + 1, if n > 2  
holds for all odd n, and for even n, just subtract one for the starting square.
 
Chris
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Knight on an infinite chessboard  
« Reply #9 on: Apr 24th, 2003, 10:36am »
Quote Quote Modify Modify

But the original square is already included. That is, f(0) = 1.
 
Let's generalize the question:
 
Consider a knight moving on an infinite chessboard.  
How many squares can it arrive at after precisely n moves given that:
 
1) it can double back and re-visit squares?  
 
2) it cannot double back and re-visit squares?
 
3) we also count every square that it has visited?
 
Also, 4) how many for n or less moves?
 
1) is the original question. You are suggesting that 1) and 2) are the same sets, which seems doubtful to me.  
Have you written a program? However, 3) and 4) would appear to be identical. [i][/i]
« Last Edit: Apr 25th, 2003, 5:34am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
cho
Guest

Email

Re: Knight on an infinite chessboard  
« Reply #10 on: Apr 24th, 2003, 11:27am »
Quote Quote Modify Modify Remove Remove

In #2, of course, you can never end up back at square one because it's been visited, but any other square that can be reached can be reached without using a square twice.  
For example: Move 1 could put you at 2,1 from the start. Move 3 could put you there by going 2,-1; 4,0; 2,1. For any square you want to reach 2 or 4 or 6 or 8 moves after the move that would most quickly put it there, you just move 1 or 2 or 3 or 4 moves beyond it and come back on a parallel route.
Your #3 is just each number added to the previous term in the series. Even I can do that math: 14x2-6x+5.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board